概要
公開鍵暗号方式のひとつであるRSA
暗号化する鍵(公開鍵)と復号する鍵(秘密鍵)が違うってどういうしくみなの
Goal
- なぜ世の中で公開鍵暗号が利用されているのかがわかる
- 公開鍵で暗号化したものが別の鍵である秘密鍵で復号できる仕組みがわかる
- 鍵を公開してるのに、なぜ解読されないかがわかる
- PEMがちょっとだけわかる
諸注意
ほぼ独学
自分の中では納得しているが、漏れ等あるかもしれない。。
随時頂いたコメントで記事を修正してます。
コメントありがとうございます。
RSA暗号が生まれた背景(共通鍵暗号方式の課題)
鍵配送問題
「秘密」を守るためには鍵という「秘密」を相手と共有しなければならないというジレンマ
通信経路は安全ではないという前提(じゃなきゃ暗号化しなくていい)
鍵の配送など些末な話に聞こえるかもしれないが、この問題こそは戦後の暗号作成者にとって最優先の重要課題だった。第三者に鍵を配送してもらわなければ秘密の通信ができないなら、そこがセキュリティという鎖の中でもっとも弱い環になる。企業が頭を抱えたのも無理はない。政府がありったけの資金をつぎ込んでも鍵の配送に苦労しているというなら、民間企業はどうやったら破産せずにやっていけるのだろう？
サイモン・シン. 暗号解読（下）（新潮文庫）
この課題を解決したのが公開鍵暗号の考え方である。
鍵配送問題は解決不可能だという意見もあるなかで、一九七〇年代半ば、独自の路線を行く人々がこの困難に立ち向かい、みごとな解決法を見出した。彼らが工夫した暗号化システムは、あらゆる論理の裏をかくようなものだった。コンピューターは暗号化のプロセスを様変わりさせたが、暗号分野における二十世紀最大の革命は、鍵配送問題を克服するテクニックが開発されたことだろう。実際、鍵配送問題の解決は、二千年以上前に単アルファベット暗号が発明されて以来最大の快挙とされているのである。
サイモン・シン. 暗号解読（下）（新潮文庫）
公開鍵暗号
有名なので、細かいことは言及しません
暗号化の鍵(公開鍵)と、復号の鍵(秘密鍵)を別のものとする暗号方式
公開鍵はその名の通り、知られてもいい情報になっており、だれでもその鍵を利用して、暗号化ができる
が、復号できるのはその公開鍵と対になっている秘密鍵のみ
つまり、秘密となる鍵の配送をすることなく、特定の人物と暗号化通信が可能となる
- 送信者が必要なのは公開鍵のみ
- 受信者が必要なのは秘密鍵のみ
- 盗聴者に知られて困るのは秘密鍵のみ
- 公開鍵は盗聴者に知られてもOK
公開鍵暗号のアイデア(定義)自体は、Diffie-Hellman鍵交換と同じ論文で発表された
公開鍵暗号の実装としてはじめて発表されたものがRSA
RSA
1978年、ロナルド・リベスト、アディ・シャミア、レオナルド・エーデルマンによって発表された
(RSAはそれぞれの頭文字)
彼らはRSAデータセキュリティ社を設立し、1983年、RSAアルゴリズムに対するアメリカにおける特許を取得している
(2000年に期間満了)
暗号化、復号の方法
RSAではどのようにして2つの鍵で暗号通信を実現しているのじゃ
暗号化
RSAでは平文$M$(Message)を累乗してmodをとることで暗号化し、暗号文$C$(Cryptogram)を計算する
$$C \equiv M^E \pmod N$$
このパラメータ$E$(Encrypt)と$N$が暗号化の鍵となる
復号
復号も暗号化と同じ操作
$$M \equiv C^D \pmod N$$
このパラメータ$D$(Decrypt)と$N$が復号の鍵となる
つまり
RSAでは、こういう操作をしていることになる
$$M \equiv M^{E \cdot D} \pmod N$$
$E$乗したら変な数字になって(暗号化)、
その数字を$D$乗したらもとの数字にもどってくる(復号)
(山手線みたいだね)
Q. そんなにうまいこといくの?
A. うまいこといくように$E$、$D$、$N$を選びます
先に結論
任意の正の整数$a$と、相違なる素数$p$、$q$の積$n$において以下の式が成り立つ
$$a^{(p-1)(q-1)v + 1} \equiv a\pmod n$$
ただし、$v$は任意の整数
つまりどんな正の整数も$(p-1)(q-1)v + 1$乗して、$n$で割った余りはもとの数字に戻る
$n$が$10$($p:2$、$q:5$)の場合は、$4v+1(5,9,13...)$乗したときにもとの数字に戻ることになる
なので、$E$、$D$を掛けたら$(p-1)(q-1)v + 1$になるような$E$、$D$、$p$、$q$の組み合わせを探せばRSAで暗号化、復号ができます
これがなんで成り立つのかをこれから調べていきます
まずは試してみて感覚をつかむ
1~9の数字(平文と仮定)を用意し、1乗、2乗...9乗してみる
縦に向かって1乗、2乗...って
1 2 3 4 5 6 7 8 9
------------------------------------------------------------------------------------------
1| 1 2 3 4 5 6 7 8 9
2| 1 4 9 16 25 36 49 64 81
3| 1 8 27 64 125 216 343 512 729
4| 1 16 81 256 625 1296 2401 4096 6561
5| 1 32 243 1024 3125 7776 16807 32768 59049
6| 1 64 729 4096 15625 46656 117649 262144 531441
7| 1 128 2187 16384 78125 279936 823543 2097152 4782969
8| 1 256 6561 65536 390625 1679616 5764801 16777216 43046721
9| 1 512 19683 262144 1953125 10077696 40353607 134217728 387420489
次に全部の値の10で割った余りを求める
1 2 3 4 5 6 7 8 9
------------------------------------------------------------------------------------------
1| 1 2 3 4 5 6 7 8 9
2| 1 4 9 6 5 6 9 4 1
3| 1 8 7 4 5 6 3 2 9
4| 1 6 1 6 5 6 1 6 1
5| 1 2 3 4 5 6 7 8 9
6| 1 4 9 6 5 6 9 4 1
7| 1 8 7 4 5 6 3 2 9
8| 1 6 1 6 5 6 1 6 1
9| 1 2 3 4 5 6 7 8 9
5乗の行と9乗の行に注目
1 2 3 4 5 6 7 8 9
------------------------------------------------------------------------------------------
5| 1 2 3 4 5 6 7 8 9
9| 1 2 3 4 5 6 7 8 9
計 算 前 に も ど っ て る
$N=10$のとき、$E \cdot D$ が$5$や、$9$になるような数字を使えば、1~9の数字であればRSAのアルゴリズムで、暗号化、復号ができた
これが2つの鍵で暗号化、復号を実現している仕組み
フェルマーの小定理、オイラーの定理
というやつで説明できるらしい
フェルマーの小定理
$p$を素数とし、$a$を$p$でない整数($a$と$p$は互いに素)とするときに
$$a^{p-1} \equiv 1 \pmod p$$
が成立する
オイラーの定理とは
$n$が正の整数で、$a$と$n$を互いに素な正の整数としたとき
$$a^{\varphi(n)} \equiv 1\pmod n$$
が成立する
ここで$\varphi(n)$はオイラー関数である
フェルマーの小定理を合成数に拡張したもの
オイラー関数
オイラーのφ関数 - Wikipedia
正の整数$n$に対して1から$n$までの自然数のうち、$n$と互いに素なものの個数を$\varphi(n)$として与える関数
たとえば、$\varphi(10)$は$4$である $({1,3,7,9})$
また、オイラー関数は以下の性質があることが知られている
- $n$が素数の場合、$\varphi(n)$は$n-1$となる
- $n$,$m$が互いに素な自然数の場合、$\varphi(nm)$は$\varphi(n)\varphi(m)$となる
オイラーの定理の式をごにょごにょ
両辺を任意の整数$v$で累乗し、両辺に$a$をかけると以下の式が得られる
$$a^{\varphi(n)v + 1} \equiv a\pmod n$$
も ど っ た
つまり、
任意の正の整数$a$に対して、$\varphi(n)v+1$乗すると、法$n$のもと合同となる(もとに戻る)
(ただし、$v$は任意の整数、$n$は$a$と互いに素となる正の整数)
→ $n$を素数にすればいいね。
RSAで利用する$E$、$D$、$N$とは以下のような関係になる
$$E \cdot D = \varphi(N)v + 1$$
以下の一次不定方程式を満たす$E$、$D$ならOK
$$E \cdot D - \varphi(N)v = 1$$
解を整数にするために、$E$(もしくは$D$)は$\varphi(n)$と互いに素になるように選択する
一次不定方程式ax+by=cの整数解 | 高校数学の美しい物語
$E$も素数にしちゃえばいいね
なるほどそういうしくみなのね
これだと問題があります
秘密鍵の安全性
RSA暗号は公開鍵暗号方式です
$E$、$N$は公開鍵です
Q. 公開鍵から秘密鍵ばれない?
A. $\varphi(N)$がわかれば以下の式で簡単に解かれちゃう
$$E \cdot D - \varphi(N)v = 1$$
$N$が素数だと以下より簡単に解けてしまう
$$\varphi(N)=N-1$$
安全性の根拠
$N$は公開するけど、$\varphi(N)$が計算出来ないようにすればいい
そんなことが可能なのか
RSA暗号とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。
-- RSA暗号 - Wikipediaより
RSAでは$N$には桁数が大きい素数$p$、$q$の合成数を選択します
$\varphi(n)$を計算するためには、素因数分解が必要となる
ただし、$p$、$q$が既知の場合は$(p-1)(q-1)$で計算できる
つまり、$N$を公開しても$p$、$q$を知らなければ$\varphi(N)$を効率的に計算することは困難である
ちょとまて
任意の正の整数$a$に対して、$\varphi(n)v+1$乗すると、法$n$のもと合同となる(もとに戻る)
(ただし、$v$は任意の整数、$n$は$a$と互いに素となる正の整数)
$n$は素数じゃないとだめじゃ。。
aとnが互いに素という条件が厳しい...
任意の$a$に対して成立しないと複合できない箇所がでちゃう
任意の$a$に対して、素数$p$、$q$の積$n$で以下の式が成立すればいい
$$a^{\varphi(n)v + 1} \equiv a\pmod n$$
つまり以下が$n$で割り切れればいい
$$a^{\varphi(n)v + 1} - a$$
ちょと式変形
$$a(a^{\varphi(n)v} -1)$$
前提として、$a$と$n$が互いに素ではないと仮定する(互いに素なら成り立つから)
$a$と$n$が互いに素ではないので、$a$が$p$の倍数であると仮定する
$a(a^{\varphi(n)v} -1)$は$a$の倍数(つまり$p$の倍数)なので$p$で割り切ることができる
なので以下は成立
$$a^{\varphi(n)v + 1} \equiv a\pmod p$$
あとは$a$の係数$a^{\varphi(n)v} -1$を$q$で割り切れれば良い
つまり以下を証明する
$$a^{\varphi(n)v} \equiv 1 \pmod q$$
オイラー関数の特性より$\varphi(n)$は以下のように変形できる
$$\varphi(n)=(p-1)(q-1)$$
よってこう
$$a^{(p-1)(q-1)v} \equiv 1 \pmod q$$
フェルマーの定理より証明完了
$$a^{(p-1)(q-1)v} = (a^{(q-1)})^{(p-1)v}\equiv 1 \pmod q$$
まとめ
任意の正の整数$a$と、相違なる素数$p$、$q$の積$n$において以下の式が成り立つ
$$a^{\varphi(n)v + 1} \equiv a\pmod n$$
RSAで利用する$E$、$D$、$N$とは以下のような関係になる
$$E \cdot D - \varphi(N)v = 1$$
解を整数にするために$E$には素数を用いればOK
$\varphi(N)$の計算も困難..!
なるほどそういうしくみなのね
実際に鍵をつくってみる
しくみはなんとなくわかったので、実際に鍵をつくってみる
1. Nをつくる
大きな素数を2つ用意
(計算がめんどくさいので小さめにやります、、)
- $p = 17$
- $q = 19$
- $N = pq = 323$
2. φ(N)をもとめる
$$\varphi(pq) = (p-1)(q-1) = (17 - 1)(19 - 1) = 288$$
が、実際のRSAアルゴリズムではここで、$p-1$と$q-1$の最小公倍数$L$を計算する
これは$v$が任意の整数であるため、最小公倍数$L$でも以下のように式が成り立つためである
$$\varphi(n)v + 1 = (p-1)(q-1)v + 1 = Lv' + 1$$
最小公倍数は
$$L = lcm(p-1,q-1) = 144$$
3. Eを決定する
$L$と互いに素となり、$L$よりも小さな数字を選ぶ
$5, 7, 11, 13, 17, 19, 23, 25...$
- $E = 5$
※実際のRSAでは基本固定の素数が使われます$(3, 17, 65537)$
強度に影響しないのと、数が小さく、ビットが立たない数字のほうが乗算速度がはやいため
4. Dをもとめる
以下を$v$を任意の整数として解く(ユークリッド互除法とか)
$$5D - 144v = 1$$
- $v=1$
- $D=29$
5. 完成
公開鍵:
- $E: 5$
- $N: 323$
秘密鍵:
- $D: 29$
- $N: 323$
つくった鍵であそぶ
平文
-
A
Aは0x41=65
暗号化
$$65 ^ 5 \mod{323} = 12$$
復号
$$12 ^ {29} \mod{323} = 65$$
無事もどせたね
安全性(その1)
秘密鍵$29$を公開鍵から計算するためには、以下の式を解く必要があり、
$$5D - \varphi(323)v = 1$$
$\varphi(323)$を効率的に解くことができないというはなし(素因数分解問題)
安全性(その2)
直接、以下の式で平文を求める計算も、離散対数問題に帰着する
$$12 = M ^ 5 \mod{323}$$
休憩
冪剰余
$a ^ b \pmod c$は冪剰余と呼ばれる演算
工夫で高速化できる
Pythonでは関数がある
組み込みのpowに実は第三引数がある
組み込み関数 — Python 3.7.2 ドキュメント
% python
Python 3.6.4 |Anaconda, Inc.| (default, Jan 16 2018, 12:04:33)
[GCC 4.2.1 Compatible Clang 4.0.1 (tags/RELEASE_401/final)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> pow(65, 5)
1160290625
>>> pow(65, 5, 323)
12
実際の鍵を見てみる
いつもこんなのやるはず
% ssh-keygen -t rsa -b 4096 -N "" -C "xxxxx" -f ./id_rsa -- INSERT --
Generating public/private rsa key pair.
Your identification has been saved in ./id_rsa.
Your public key has been saved in ./id_rsa.pub.
The key fingerprint is:
SHA256:Bd1e7wEEZ1F+ztihtf+gdMmrWSQvM8k4mwjTO9nri9Q @xxxx
The key's randomart image is:
+---[RSA 4096]----+
| .. oo=o. |
| .. +.o |
| .. ..=.|
| . . o*=|
| S ..oo=|
| . . o * .o|
| o ooE B B .|
| +o+.= O o.|
| +o*o+.. .|
+----[SHA256]-----+
こんなのができてるはず
公開鍵
ssh-rsa AAAA...@xxxx
秘密鍵
-----BEGIN OPENSSH PRIVATE KEY-----
...
-----END OPENSSH PRIVATE KEY-----
それかこれ
% openssl genrsa -out private.key 4096 && openssl rsa -in private.key -pubout -out public.key
Generating RSA private key, 4096 bit long modulus
.................................................................++
.....................++
e is 65537 (0x10001)
writing RSA key
公開鍵
-----BEGIN PUBLIC KEY-----
...
-----END PUBLIC KEY-----
秘密鍵
-----BEGIN RSA PRIVATE KEY-----
...
-----END RSA PRIVATE KEY-----
フォーマットはいろいろあるが、全てRSAの鍵
bitというのは$N$のbit数
ちょと4096bitだと見るのもつらいので小さくつくる
ssh-keygenは1024bitが最小、opensslは32bit
% openssl genrsa -out private.key 32 && openssl rsa -in private.key -pubout -out public.key -- INSERT --
Generating RSA private key, 32 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)
writing RSA key
公開鍵
-----BEGIN PUBLIC KEY-----
MCAwDQYJKoZIhvcNAQEBBQADDwAwDAIFALzHJxkCAwEAAQ==
-----END PUBLIC KEY-----
秘密鍵
-----BEGIN RSA PRIVATE KEY-----
MCwCAQACBQC8xycZAgMBAAECBDE1VjECAwDs5wIDAMv/AgITwwICBbMCAwCbNQ==
-----END RSA PRIVATE KEY-----
これはpemと呼ばれるエンコード形式
バイナリをBASE64でテキスト化してる
公開鍵のバイナリはPKCS#8というフォーマットらしい
こんなかんじらしい(RFC読んでもわからん)
ASN.1 key structures in DER and PEM - Knowledge Base - mbed TLS (Previously PolarSSL)
PublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier,
PublicKey BIT STRING
}
AlgorithmIdentifier ::= SEQUENCE {
algorithm OBJECT IDENTIFIER,
parameters ANY DEFINED BY algorithm OPTIONAL
}
バイナリ読むのはつらいのでopensslの機能を使う
% openssl rsa -pubin -in public.key -text -noout -- INSERT --
Public-Key: (32 bit)
Modulus: 3167168281 (0xbcc72719)
Exponent: 65537 (0x10001)
$N$が$3167168281$で、$E$が$65537$となっている
秘密鍵はPKCS#1
こんなかんじ
RFC 8017 - PKCS #1: RSA Cryptography Specifications Version 2.2
RSAPrivateKey ::= SEQUENCE {
version Version,
modulus INTEGER, -- n
publicExponent INTEGER, -- e
privateExponent INTEGER, -- d
prime1 INTEGER, -- p
prime2 INTEGER, -- q
exponent1 INTEGER, -- d mod (p-1)
exponent2 INTEGER, -- d mod (q-1)
coefficient INTEGER, -- (inverse of q) mod p
otherPrimeInfos OtherPrimeInfos OPTIONAL
}
% openssl rsa -in private.key -text -noout
Private-Key: (32 bit)
modulus: 3167168281 (0xbcc72719)
publicExponent: 65537 (0x10001)
privateExponent: 825579057 (0x31355631)
prime1: 60647 (0xece7)
prime2: 52223 (0xcbff)
exponent1: 5059 (0x13c3)
exponent2: 1459 (0x5b3)
coefficient: 39733 (0x9b35)
$p$、$q$がそれぞれ$60647$と$52223$のようです
$D$は$825579057$ですな
ssh-keygenで作ったほうのフォーマットはこれ(厳密にはちょと違いそうだけど、バイナリ自体のフォーマットはこれ)
AAAAからはじまるやつ
RFC 4716 - The Secure Shell (SSH) Public Key File Format
ssh-keygenがpkcs#8で吐けるので変換する
4096bitほどにもなると16進数になっててわけわからん
% ssh-keygen -e -f id_rsa.pub -m pkcs8 | openssl rsa -pubin -text -noout -- INSERT --
Public-Key: (4096 bit)
Modulus:
00:c3:ca:4c:89:37:11:54:dc:b3:a4:79:35:6d:5b:
de:21:7e:0d:34:73:e5:f7:ee:fa:8c:3a:ea:3c:4a:
81:ba:24:a0:d8:a6:ea:3f:30:0c:99:2d:57:1d:54:
d3:0f:aa:c2:3e:e7:8f:7c:0b:3d:3b:0c:b2:48:1e:
ed:d5:dd:c8:a5:29:c8:b2:ee:5f:bc:81:ce:bb:00:
90:80:02:c3:69:47:42:9a:02:95:fe:d7:06:1a:e9:
e7:cb:c2:d1:4b:91:d2:16:c2:d2:09:3f:d8:6b:d4:
7f:cd:ec:87:97:40:e9:6d:44:ba:88:a9:a7:ee:60:
94:8b:b8:2b:73:19:6e:ca:ff:6a:9c:00:18:14:29:
0f:10:21:c1:da:67:3c:cf:5d:e2:6b:03:c0:2e:40:
6f:15:e3:55:39:24:c7:03:b0:b1:dc:ba:76:02:49:
10:f8:fa:72:63:8e:c1:7d:01:0c:33:db:be:49:23:
0d:f5:49:0a:c3:c0:9d:9d:a4:83:1a:28:11:b9:7f:
d1:33:6a:b3:dc:e1:e1:85:72:2c:99:ef:da:bf:20:
11:8e:dc:d2:07:2b:dc:96:df:29:8f:9e:bd:23:a3:
68:12:b0:dd:a9:07:64:21:76:f7:a1:0c:74:dd:1f:
13:2a:b9:b0:a9:51:5b:c9:3f:df:c6:92:8e:f7:63:
e5:ac:fb:56:40:40:30:6d:51:83:6e:57:2c:75:70:
64:97:c1:e4:3a:8d:bb:d9:96:a8:cd:ae:0d:df:db:
96:ee:31:20:e8:14:39:5a:9c:d9:54:3b:bf:2f:04:
97:13:e8:91:b7:69:83:47:38:ff:3a:8c:ac:a4:e7:
2e:a7:ef:6c:4b:77:9d:c6:ff:8e:a1:24:60:ed:b6:
b0:46:10:b7:e7:dd:96:00:a7:10:b0:80:1c:f9:ca:
a1:2c:0e:6a:1b:58:89:cf:54:e3:8a:c0:60:92:c1:
61:e8:cc:07:fa:c9:48:55:18:66:19:ce:cb:30:59:
db:73:e2:da:be:9b:28:c7:b8:60:a5:95:d2:1c:4d:
00:27:57:db:d8:50:d9:1f:7c:7c:bb:6e:23:6a:c7:
e4:6f:4a:c7:44:93:3b:2f:01:5f:a6:ce:59:16:d0:
38:3f:a0:74:57:56:a0:16:dc:e7:81:af:d4:b3:44:
a0:ef:53:bb:a0:18:0a:1f:21:42:d9:65:d9:45:cd:
b4:db:2e:7a:c4:4d:81:81:ad:a6:74:13:67:d0:95:
8f:8f:05:e5:b9:0a:5f:e0:9a:5b:00:05:b8:74:be:
ec:be:46:7f:c1:3f:7b:e9:03:24:8f:ba:71:13:e2:
59:e1:62:89:87:03:6c:74:8e:1a:7e:fb:fb:68:80:
b0:02:2b
Exponent: 65537 (0x10001)
普段使ってる鍵ファイルに何が書いてあるかはこんなかんじ
所詮RSAなので数字が書いてあるだけ
RSAの特徴
おっそい 
共通鍵暗号方式と比較して数百~数千倍遅いらしい
そのため一般的にRSAは通信鍵ではなく、鍵暗号鍵として利用される
公開鍵が信用できるとは限らない 
これは、RSAではなく、公開鍵暗号方式の問題
たしかに鍵配送をすること無く安全に暗号通信できるとはいえ、公開鍵が本当に通信したい相手のものかどうかの確認はしていない
(いくら暗号しても相手を間違えちゃ意味ない)
このために、公開鍵を確認する仕組みとして、公開鍵証明書(デジタル証明書)という仕組みがある
(これもRSAによって支えられている)
またこんど。
平文と暗号文の定義域が等しい 
平文と暗号文に区別がない
平文を暗号文と仮定して、復号することも可能
これによりRSAは、デジタル署名の付与が可能
デジタル署名
の話はまたこんど。。
RSAを利用したデジタル署名は、秘密鍵を持っているということはつまり本人だよねっていう考え方で認証の仕組みを提供する方法
簡単に言うと、
平文に対して秘密鍵でもって復号処理を施すことで、作成者が秘密鍵所持者であることを証明する
っていうこと(本人確認は公開鍵で暗号化すればいいよね)
本文の改ざんも検知できる
平文と暗号文を同じように扱えるRSAだからできること
※デジタル署名には、RSA以外で実現している方式もあるため、これがデジタル署名アルゴリズムの定義ということではない。
まとめ
考えた人すごすぎる
DH鍵交換、デジタル署名など周辺も調べねば。
References
暗号技術入門 第3版 秘密の国のアリス
暗号解読（上）（新潮文庫）-サイモン・シン
暗号解読（下）（新潮文庫）-サイモン・シン