RSAの基礎と仕組み
関係式
pとqは素数として，n = p * q ... (1)
e*d = k * (p-1) * (q-1) + 1 ... (2)
ここで，kは任意の自然数である．このような関係があるとき
A = ( A^(e*d) ) % n ... (2)
という関係が得られる． これは，Aを何乗かして，nのモジュロ（剰余，余り）を計算すると，元のAに戻ること表している．
何乗すれば良いかは，nの元になっている2つの素数pとqがわかれば，式(2)の通り，簡単に求められる．なんか不思議．
次に，
α = ( A^e ) % n ... (3) [暗号化]
の操作をAの暗号化と考え，αを暗号文とする． 実際，e乗した結果は乱数のように思える．
復号はαに対して次の計算をすれば良い．
A = ( α^d ) % n ... (4) [復号]
式(2)と式(3)の関係より，式(4)で元のAに戻せることがわかる．
超簡単！
公開鍵・秘密鍵との関係
公開鍵と秘密鍵で説明した通り， 公開鍵を利用して，平文(A)を暗号化したい．式(3)の暗号化に必要なのは，平文(A)の他に，nとeであることがわかる．そのため，nとeを公開鍵と考える．公開鍵と秘密鍵で説明した通り， 秘密鍵を利用して，暗号文(α)を復号したい．式(4)の復号に必要なのは，暗号文(α)の他に，nとdであることがわかる． ところで，運用上，秘密鍵から公開鍵を作成したい場合が多い．計算に必要なのは，nとdでけであるが，公開鍵を生成するための情報eを含めた，nとe,dを秘密鍵と考える．
公開鍵:n,e
秘密鍵:n,e,d
このように考えると，平文(A)を公開鍵で，暗号化し，秘密鍵を用いて，復号することができる．
公開鍵から秘密鍵を生成できるか？
今，dとAがわからないとする．公開鍵(n,e)は誰でも知っているとする．このような状態で暗号文(α)から，平文(A)を計算することができるか？
dがわかれば，簡単に暗号文(α)から平文(A)を計算することができてしまう． そのため，結局，公開鍵の情報(n,e)から，dを求めることができるかということと同じである．
式(2)からnの元になっている2つの素数pとqがわかれば，dが簡単にわかってしまう． しかしながら，大きな数の素因数分解(nからpとqを求めること)は非常に時間がかかり，簡単ではないことが知られている．
つまり，公開鍵から，復号するのに必要な情報dを求めることは非常に困難であることになる．
ところで，「不可能」ではなく，実用上は「困難」で十分である． 例えば，「金庫」から「鍵」を作成することは「不可能」ではなく，「困難」である． しかしながら，現実的に「金庫」は十分実用的である．
平文(A)がばれちゃうんじゃない？
ところで，復号するのに必要な情報dを，わざわざ求めなくても，nがわかっているのであれば，適当に暗号文を何乗かしていけば，平文(A)が「見えて」しまう．何乗したときが，平文(A)なのかはわからないが，「暗号化」により「暗号文」がランダムになるのであれば，この性質を逆に利用して，暗号文を適当に何乗かしていき，意味のありそうな情報になったかどうかをチェックしていけば良い． そうすることにより，復号もできるし，復号に必要な情報dも求められてしまう．
しかし，仮に平文(A)がもともと，ランダムであれば，適当に何乗かしても，平文(A)に戻ったかどうかはわからず，復号に必要な情報dも求められない．
ランダムな情報を平文(A)にすることも重要である．
チャレンジ・レスポンス認証とパスフレーズ へ
