0と1の羅列(現代暗号もコンピュータを使います)

今回のクイズ1

「442, 1982, 911, 442, 400, 911, 442」をそれぞれ257乗して2021で割った余りを以下の規則に従ってアルファベットにしてみましょう。
A=260、B=264、C=268、…、Z=360
どんな文字列になりましたか?

 

RSA暗号方式について解説

注:この文章には数学的な内容がたっぷり書かれています。手っ取り早く答えをご覧になりたい方はまでスクロールしてください。
さて、冒頭の問題を解説するために、RSA暗号/署名について詳しく説明してみましょう。

RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。暗号とデジタル署名を実現できる方式として最初に公開されたものである。Wikipedia RSA暗号

公開鍵で19^3 mod 55を計算し、秘密鍵で39^7 mod 55を計算する

素数p,q(図では5, 11)を秘密裏に用意し、積をn(5×11 = 55)とします。
公開鍵eと秘密鍵dを、e×d-1がp-1でもq-1でも割り切れるように選択します。
(e = 3, d= 7とすれば、3×7 = 4×5 + 1 = 10×2 + 1)
nとeが公開鍵となります。p, q, dは秘密のままです。
C ≡ M^e (mod n) で暗号化、M ≡ C^d (mod n)で平文に戻します。
(「N mod n」で「Nをnで割った余り」を表しています。)

これはフェルマーの小定理を使っています。

p を素数とし、a を p の倍数でない整数(a と p は互いに素)とするときに、a の p − 1 乗を p で割った余りは 1 であるというもの。Wikipediaフェルマーの小定理

(M^e)^d = M^(ed) = M^(xφ+1) ≡ M (mod n) (φはp-1とq-1の最小公倍数)

なお、Mがpの倍数であったとしても、M^(ed) ≡ 0 (mod p)、なおかつM^(ed) = M^(y(q-1)+1) ≡ M (mod q)が成り立ちますので、0 ≦ r < n の条件下で、r ≡ 0 (mod p)かつr ≡ M (mod q)を満たすrはMしかありません。

暗号鍵を使って暗号を作るのと、復号鍵を使って平文に戻すのは互いに逆の操作ですが、用途によってどちらを公開するかが違います。

実際に19をこの方法で暗号化すると19^3 ≡39となり、逆に39^7 ≡19となります。一方、暗号「39」と暗号鍵「3」からは平文「19」を作れませんし、平文「19」と復号鍵「7」からは暗号「39」を作れません。

2つの素数pとqを掛け算するのは簡単ですが、公開鍵nとeから秘密鍵dを求めるには、nをpとqに素因数分解しなければならず、より手間がかかります。これらの計算の手間の非対称性が、公開鍵暗号であることの根拠なのです。

なお、実際の利用時は暗号化前にパディング(例:OAEP)を施し、暗号の解読をより困難なものとしています。

 

RSA署名と、RSA暗号との関係

RSA暗号方式の秘密鍵で復号する処理と、RSA署名の秘密鍵で暗号化する処理は本質的には同じ

RSA署名は秘密鍵で暗号化する方式を取っていますが、RSA暗号の復号鍵(秘密)を使って署名を生成している、と解釈することもできます。
M ≡ C^d (mod n)で署名値を生成し、C ≡ M^e (mod n) で検証を行います。

 

クイズ1の答え

さて、冒頭の問題ですが、「ITAISAI」になったでしょうか?(ドラッグすると出てきます)ここまではWindowsの関数電卓で計算できますね?
手計算なら「2乗して2021で割った余りを求める」を8回やって、元の数字を掛けて2021で割った余りを求めることになります。
C^257 = C^(2^8+1) = ((((((((C^2)^2)^2)^2)^2)^2)^2)^2)×C

 

今回のクイズ2

さて、ここからは秘密鍵を求める問題です。
さて、暗号「442, 1982, 911, 442, 400, 911, 442」を作るのに、元の数字を何乗したでしょうか?
これが解けたら「BLOG」「JAPAN」を同じ方法で暗号化してみましょう。

答えはこちら
2021 = 45^2 – 2^2 = 47×43から、lcm(46, 42) = 23×21×2 = 966
(lcm: 最小公倍数)
257×857 = 228×966+1で、暗号化には元の数字を857乗して2021で割ったことがわかります。

さすがに857乗をそのまま計算するには桁が大きすぎますので、以下のように、「奇数から1を引いて、再び奇数になるまで2で割り続ける」ことで指数を小さくしていきます。

  1. M^857 = M^(107×2^3+1) = ((((M^107)^2)^2)^2)×M
  2. M^107 = M^(53×2+1) = ((M^53)^2)×M
  3. M^53 = M^(13×2+1) = (((M^13)^2)^2)×M
  4. M^13 = M^(3×2^2+1) = (((M×M×M)^2)^2)×M

例えば、

  1. 292^13 = (((292×292×292)^2)^2)×292 ≡ (((382×292)^2)^2)×292 ≡ ((389^2)^2)×292 ≡ (1767^2)×292 ≡ 1865×292 ≡ 931
  2. 292^53 = (((292^13)^2)^2)×292 ≡ ((931^2)^2)×292 ≡ (1773^2)×292 ≡ 874×292 ≡ 562
  3. 292^107 = ((292^53)^2)×292 ≡ (562^2)×292 ≡ 568×292 ≡ 134
  4. 292^857 = ((((292^107)^2)^2)^2)×292 ≡ (((134^2)^2)^2)×292 ≡ ((1788^2)^2)×292 ≡ (1743^2)×292 ≡ 486×292 ≡ 442

となります。

掛け算をする度に、2021で割った余りに変換することも忘れずに行ってください。

「BLOG」→(数字化)→「264, 304, 316, 284」→(暗号化)→「595, 499, 943, 1568」
「JAPAN」→(数字化)→「296, 260, 320, 260, 312」→(暗号化)→「230, 911, 1351, 911, 127」

 

今回は「2021」という4桁の合成数を使っているため、人力でも素因数分解をして秘密鍵を求めることはできますが、実際はもっと大きい整数が使われています。鍵長が2048ビット(2^2048 ≒ 3.2×10^616)ともなれば、今日のコンピュータでも解読は困難なものとなっております。