「非常に大きな数の素因数分解が困難なことを利用した公開鍵暗号方式(H23春FE午前問42)」は何か?
これを開発したのはMITの助教授であったロナルド・リベスト(Ronald Rivest)、アディ・シャミア(Adi Shamir)、レオナルド・エーデルマン(Lenonard Adleman)の3人の名前。3人の頭文字をとってRSAとしています。
ロナルド・リベスト(Ronald Rivest)はRC4の開発者でもある(はず)。
RSAは公開鍵暗号方式のスタンダード。RSAの問題点であった処理の複雑さを、楕円曲線暗号は改善しています。ただ、セキュリティ強度は不明です。
(1)仕組み
 シンプルな仕組みであるが、それでも解説しようとすると数ページに及ぶため基本原理のみ説明します。 
 整数を1乗2乗3乗していくと次の結果になります。今回は2と7を紹介。
暗号化
文字
1乗2乗
3乗
4乗
5乗
6乗
7乗
8乗
9乗

2
2
4
8
16
32
64
128
256
512
7
7
49
343
2401
16807
117649
823543
5764801
40353607

これを見ると、1乗、5乗、9乗の1桁目は全て同じである。
この原理は、全ての数についてあてはまる。
ということは、暗号化するときは3乗し、復号するときは1乗すればよい。
(※結果の値は、1桁目のみ)
2→(3乗)→6→(1乗)→2
7→(3乗)→1→(1乗)→7
3が秘密鍵で1が公開鍵である。これが暗号化に使う鍵と復号に使う鍵が異なる公開鍵暗号の仕組みである。
15863853

でもこんなに簡単な仕組みだったら誰でも1乗して復号できますね。




そう。実際にはもっと大きな数(例えば128ビット)で行われるので大丈夫。
例えば、13×17を例にすると、同じ数字になる間隔は192です。
※これは、(13-1)×(17-1)=192で求められるようです。
なので、復号する側は、何乗すればいいかを192回試す必要があり、かなり大変です。

2桁×2桁程度でも大変そうなので、128ビットだったらとても計算できないですね。
たしか、素因数分解の難しさを利用しているって聞きましたが。

13×17という素因数分解ができれば、同じ数字になる間隔が (13-1)×(17-1)=192と割り出せてしまいます。だから、素因数分解の難しさが大前提になります。

以上、ほんの一部だけ説明しました。
詳しい内容まで踏み込む必要はありません。雰囲気を感じていただくだけでいいです。