RSA暗号では、暗号化と復号のときにそれぞれ2つの数値を使う。そのうちの1つ \(n\) は共通で、\(e\) は
encode, \(d\) は
decodeの頭文字。
暗号化の鍵 : \(e\) と \(n\)
復号の鍵 : \(d\) と \(n\)
鍵の準備 (受信者が行う)
- 大きな素数 \(p\) と \(q\) を決める
- \(p\) と \(q\) の積 \(n\) と、\(p-1\) と \(q-1\) の最小公倍数 \(L\) を求める
- \(L\) と互いに素 (2以上で1以外の共通の約数を持たない) な、\(L\) より小さい正の整数 \(e\) を決める
- \(de=kL+1\) (\(k\) は整数) を満たす、\(L\) より小さい正の整数 \(d\) を求める
- 送信者 に \(e\) と \(n\) の値を渡す
例
- \(p\) と \(q\) を決める
\(p=19, q=13\) とする
(本来は非常に大きい値にするが、説明を簡単にするためここでは小さい値にする)
- \(n\) と \(L\) を求める
\(n=pq=247\)
\(L=lcm(18, 12)=36\)
(「\(lcm\)」は最小公倍数のこと)
- \(e\) を決める
\(L=36\) を素因数分解すると \(2^2\times3^2\) となる。1以外の共通の約数を持たないということは、要するに「2でも3でも割り切れない」ということ。2～35の範囲の数を書きだして2か3で割り切れるものを消していけば、5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 が残る。\(e\) はこの中のどれでもよいが、ここでは \(e=23\) とする。
| | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
30 | 31 | 32 | 33 | 34 | 35 | | | | |
- \(d\) を求める
満たすべき関係式 \(de=kL+1\) には \(d\) と \(e\) が対称な形で入っている。つまり、\(d\) も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
また、すでに分かっている値をこの関係式に入れると「\(23d=36k+1\)」、1を移項すれば「\(23d-1=36k\)」となる。つまり、候補の値それぞれについて「\(d\) を23倍して1を引き、それが36で割り切れるかどうか」を調べれば正解がわかる。
- \(d\) が \(5\) → \(23\times5-1=114\) (36で割り切れない)
- \(d\) が \(7\) → \(23\times7-1=160\) (36で割り切れない)
- \(d\) が \(11\) → \(23\times11-1=252\) (36で割り切れる) → \(d=11\)
- 送信者に \(e\) と \(n\) の値を渡す
通信路を通して \(e=23\) と \(n=247\) を送る
ステップ1と3では値を勝手に決める。
ステップ2と4で決まる値は一通りだけ。
ステップ3での「互いに素」の意味に注意。この場合は2, 3で割り切れないだけで、素数ということではない (候補のうち25, 35は素数ではない)
ステップ4で \(e\) から \(d\) を求めているので、\(e\) を通信路に通すのは危険なように見えるが、このステップには \(L\) の値も必要なので、これを通信路に通さなければ安全 (原理的には \(n\) を因数分解すれば求められるが、実際は \(n\) は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能)。
暗号化・復号の前にあらかじめ決めておくこと
- 符号を区切る桁数 \(m\) を求める
RSA暗号では、最大 \(n-1\) 種類のものを扱える。上で挙げた例では \(n=247\) であるが、7ビットで \(2^7=128\) 通り、8ビットで \(2^8=256\) 通りなので、\(m\) は7ビットとなる。
暗号化の手順
- 符号を \(m\) 桁ずつ区切り、2進数の値にする
- 変換した値を \(e\) 乗して \(n\) で割った余りを求める
- 得られた値を \(m\) ビットの符号とする
復号の手順
- 符号を \(m\) 桁ずつ区切り、2進数の値にする
- 変換した値を \(d\) 乗して \(n\) で割った余りを求める
- 得られた値を \(m\) ビットの符号とする
例 (上で挙げた \(n=247\), \(e=23\), \(d=11\) のケース (\(m\) は\(7\) になる)
暗号化
- 符号を \(m\) 桁ずつ区切り、2進数の値にする
たとえば「0001101」だったときは \((0001101)_2=(13)_{10}\) が得られる
- 変換した値を \(e\) 乗して \(n\) で割った余りを求める
|
\(13^{23}=1820828145547961773257038736474630733299942338773\)
|
で、それを247で割った余りは52になる。
- 得られた値を \(m\) ビットの符号とする
\((52)_{10}=(0110100)_2\) なので、「0110100」とする
復号
- 符号を \(m\) 桁ずつ区切り、2進数の値にする
受け取った「0110100」から \((0110100)_2=(52)_{10}\) が得られる
- 変換した値を \(d\) 乗して \(n\) で割った余りを求める
|
\(52^{11}=140007514618240900831252\)
|
で、それを247で割った余りは13になる。
- 得られた値を \(m\) ビットの符号とする
\((13)_{10}=(0001101)_2\) なので、「0001101」とする (もとの符号が得られる)
実際のRSA暗号では \(m\) は非常に大きく、300～1000程度になる。
実際に「＊＊を＊＊乗して＊＊で割った余り」をまともに求める必要はない。
「52の2乗」をA+B、つまりA(247で割り切れる部分) とB(余り)に分けて考えると、「52の3乗」は52A+52Bになるが、52Aは247で割り切れる。つまり、「52の3乗」のかわりに「52B」を247で割っても余りは同じになる。このようにしてひとつ247をかけるたびに余りを求めていけば、上の例のように巨大な数を扱わなくても最終的な余りは求められる。
例えばProcessingなら次のようになる。
int n=247;
int d=11;
int num0=52;
int num=num0;
for (int i=0; i<d; i++) {
print((i+1)+"乗して"+n+"で割った余り:");
println(num);
num=num*num0%n;
} |
1乗して247で割った余り:52
2乗して247で割った余り:234
3乗して247で割った余り:65
4乗して247で割った余り:169
5乗して247で割った余り:143
6乗して247で割った余り:26
7乗して247で割った余り:117
8乗して247で割った余り:156
9乗して247で割った余り:208
10乗して247で割った余り:195
11乗して247で割った余り:13 |