先日、私は RSA 公開キー暗号化アルゴリズムの実装を書きました。このアルゴリズムの簡単なハックも行ったので、このトピックについて短いメモを書きたいと思います。 RSA の耐タンパー性は因数分解問題に基づいています。因数分解…ひどい言葉ですね…
それほど怖いものではありません
実際、キー作成の最初の段階で 2 つの乱数を取得しますが、その数値はそれ自体と 1 つで割り切れる必要があります。 素数の数字
それらをpとqと呼びます。次に、数値 n = p *q を取得する必要があります。これはさらなるキー生成に使用され、そのキーはメッセージの暗号化と復号化に使用されます。秘密鍵と公開鍵の最終バージョンでは、数値 n は変更せずに転送されます。
RSA キーの 1 つと暗号化されたメッセージを手に持っているとします。キーから数字 n を取り出し、ハッキングを開始します。
n を因数分解
因数分解 –数値を素因数に分解すること。まず、キーから数値 n を取り出します (実際のキーでは openssl を使用して実行できます)。たとえば、n = 35 とします。次に、それを単純な因数に因数分解します。 n = 35 = 5 * 7、これがpとqです。これで、受信した p、q を使用してキーを再生成し、元の作成者の可視性を確保しながらメッセージを復号して暗号化できるようになります。
量子ビットはそれほど単純ではありません
RSA をそんなに簡単に破ることは本当に可能でしょうか?実際、いいえ、数値 p、q は意図的に大きく取られているため、古典的なコンピューターの因数分解タスクには非常に長い時間がかかります (ある程度 10 年)。 br / >ただし、Shor の量子アルゴリズムを使用すると、非常に短時間で数値を因数分解することができます。現時点では、このトピックに関する記事では、指定された数値を乗算する時間が、つまり事実上瞬時にかかると記載されています。ショールのアルゴリズムが機能するには、多数の量子ビットを備えた量子コンピューターを実装する必要があります。 2001 年に、IBM は 7 量子ビットを使用して 15 という数字を因数分解しました。したがって、この瞬間までに長い時間待つ必要がありますが、その時までにポスト量子暗号化アルゴリズムに切り替えられているでしょう。
タッチショール
ピーター・ショアが因数分解アルゴリズムについて語る
量子シミュレータでショールのアルゴリズムを試すには、ProjectQ の例には、ユーザーが入力した数値を因数分解できる shor.py の実装が含まれています。シミュレーターでは、実行時間は憂鬱ですが、量子コンピューターの動作を楽しく遊び心のあるシミュレーションのように見えます。
記事:
http://www.pagedon.com/rsa-explained-simply/my_programming/
http://southernpacificreview.com/2014/01/06/rsa-key-generation-example/
https://0day.work/how-i-recovered-your-private-key-or-why-small-keys-are-bad/
RSA の Python 実装:
https://github.com/demensdeum/RSA-Python
