この記事では、MIT Scheme言語の暗号化および復号化方法RSA [1]を解決します。 この記事で検討されているいくつかの理由により、実装を情報の暗号保護に使用することはできません。
キー生成-プライムの検索
RSAは非対称暗号化アルゴリズムを指します。公開鍵が暗号化に使用される場合、秘密鍵は復号化に使用され、逆も同様です。 最初のプロパティにより、だれでも秘密鍵の所有者のアドレスへの公開鍵を使用してメッセージを暗号化できるため、機密性が確保されます。 2番目のプロパティにより、キーの所有者は秘密キーでメッセージハッシュを暗号化できるため、誰でも暗号化されたハッシュを解読し、メッセージハッシュと比較して、メッセージが変更されたかどうかを判断できます。
キーを生成する最初のステップは、十分に大きい2つの素数pとqをランダムに選択することです。 正の整数xは、厳密に2つの異なる除数（1とx）がある場合、素数と呼ばれます。 数値の他のすべての除数は、2からxの平方根までのセグメントにありますが、このセグメントに属する単純な除数のみの多重度をチェックするだけで十分です。
（定義（プライムn）
（define（prime？n primes）
（定義（次の除数）
（または（null？除数）
（let（[divisor（car divisors）]））
（または（>（*除数除数）n）
（および（<0（剰余n（車の除数））））（iter（cdrの除数））））））
）
（元の素数）
）
（定義（iの素数i候補））
（条件
（（= in）素数）
（（prime？候補（逆素数））（iter（cons候補素数）（+ i 1）（+候補1）））
（その他（iの素数i（+候補1）））
）
）
（iter '（）0 2）
）
（素数の定義（Primes 100））
（p（車の素数）を定義する）
（define q（car（drop 10 primes））））
見つかった素数の積は、公開鍵と秘密鍵の最初の要素です。 上記のアルゴリズムにより、妥当な時間内に最初の100万個の素数のみを見つけることができます。 情報を保護するために使用されるRSA実装では、より多くの桁数の素数を見つけるために素数検索アルゴリズムが使用されます。 数を素因数に分解するための最もよく知られたアルゴリズムは、桁数の指数に比例する時間にわたって機能するという事実のため、検討中の公開鍵要素から素数のペアを回復することは不可能であると考えられている[2]。
（n（* pq）を定義）
キー生成-相互プライム検索
公開鍵と秘密鍵の2番目の要素を計算するには、nで計算されたオイラー関数[3]に等しいfi値が使用されます。 xのオイラー関数は、大きなxではなく、相互に単純な自然数の数に等しくなります。 nの場合、この量はp-1とq-1の積に等しくなります。
（定義fi（*（-p 1）（-q 1））））
公開鍵の2番目の要素は、1〜fiの範囲の乱数eであり、fiと互いに素です。 つまり、数値の最大公約数は1です。
（定義（CoprimesLess n）
（定義（アキュムレーター候補）
（条件
（（= 1候補）アキュムレーター）
（（= 1（gcd n候補））（iter（cons候補アキュムレータ）（-候補1）））
（その他（iter accumulator（-候補1）））
）
）
（iter '（）（-n 1））
）
（eを定義（車（ドロップ5（CoprimesLess fi）））））
最大の共通因子を見つけるには、ユークリッドアルゴリズムを使用できます[4]。
キーの生成-演ductionリングでの操作
数論によって研究されるオブジェクトの1つは、残基環です[5]。 kを法とする剰余環は、0からk-1までの整数と、その上での加算と乗算の演算です。 剰余環（a + b mod k）での加算は、加算結果がkより大きくなると、kが減算されるという点で、整数のグループでの加算とは異なります。その結果、この結果は再び環になります。 直観的には、リングはセグメントの両端を接続することにより取得されます。
整数のグループと同様に、剰余環の乗算は加算によって指定でき、累乗は乗算によって指定できます。 整数のグループと同様に、結果の加算および乗算演算には結合性があります。つまり、次のとおりです。
a +（b + c mod k）mod k =（a + b mod k）+ c mod k
a *（b * c mod k）mod k =（a * b mod k）* c mod k
公開鍵の2番目の要素は、nを法とする剰余環のeとの積が1になるような数値d、つまり乗法的に逆の要素でなければなりません。 拡張ユークリッドアルゴリズム[6]を使用して、このような要素の検索アルゴリズムを導入します。
（定義（MultInverseModN an）
（定義する（a-prev a r-prev r））
（if（> = 1 r）a（let *（[r-next（remainder r-prev r）]
[q（商r-prev r）]
[a-next（-a-prev（* qa））]]）
（a a-next r r-next））））
）
（let（[result（iter 0 1 na）]）（if（<0 result）result（+ n result））））
）
（定義（MultInverseModN e fi））
暗号化と復号化
RSAアルゴリズムを使用すると、0〜n-1の範囲の一連の数値Mで表されるメッセージを暗号化できます。 暗号化は、nを法とする剰余環でMを累乗eで累乗し、復号化を累乗dで行うことにあります。 乗算は結合的であるという事実により、log（x）演算に対してxの累乗を上げることができます[7]。
（定義（PowerModN abn）
（定義（iter accumulator multiplicator power）
（もし
（=パワー0）
アキュムレーター
（させる
（（new_accumulator（if（even？power）accumulator（remainder（* accumulator multiplicator）n））））））
（iter new_accumulator（*乗法と乗法）（商のべき乗2））
）
）
）
（最初の1 ab）
）
テストケース
私の例では、公開鍵はペア（250483 31）、秘密鍵はペア（250483 32191）です。 暗号化されたメッセージ123456は133240です。
参照資料
- en.wikipedia.org/wiki/RSA
- en.wikipedia.org/wiki/Integer_factorization
- en.wikipedia.org/wiki/Euler%27s_totient_function
- en.wikipedia.org/wiki/Euclidean_algorithm
- en.wikipedia.org/wiki/Modular_arithmetic
- en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- en.wikipedia.org/wiki/Exponentiation_by_squaring