読者です 読者をやめる 読者になる 読者になる

clock-up-blog

go-mi-tech

（短いビット長の）RSA暗号を解いてみる

AdventCalendar RSA セキュリティ

なんでもセキュリティ Advent Calendar 2016 15日目の記事です。

RSA鍵を作るにあたっては鍵長を十分に長くする必要があります。（この「十分に」というのは時代とともに（マシンスペックが上がるにつれ）変わっていくでしょう）

最近だと 2048ビット = 256バイトの鍵を作るのが一般的でしょうか。
この長さが短いと割と簡単に公開鍵から秘密鍵が割り出せてしまいます。

今回やること

今回は長さが十分で無いRSA公開鍵から秘密鍵を割り出す実験をしてみます。

準備

秘密鍵の準備

64ビット = 8バイトという極めて短い長さの鍵を作ります。

$ openssl genrsa -out private.pem 64
Generating RSA private key, 64 bit long modulus
.+++++++++++++++++++++++++++
.+++++++++++++++++++++++++++
e is 65537 (0x10001)

$ ls -ltr
total 4
-rw-rw-r-- 1 kobake kobake 148 Dec 11 00:09 private.pem

$ cat private.pem 
-----BEGIN RSA PRIVATE KEY-----
MD0CAQACCQCV8+qsr5+iCQIDAQABAggOcvl60pMk8QIFAMQGPRUCBQDD1RYlAgRY
cgApAgQr3+LNAgRsrJC+
-----END RSA PRIVATE KEY-----

$ openssl rsa -text -noout -in private.pem
Private-Key: (64 bit)
modulus: 10805237958393700873 (0x95f3eaacaf9fa209) ← 素数の積
publicExponent: 65537 (0x10001)
privateExponent: 1041168769790190833 (0xe72f97ad29324f1) ← これが秘密鍵バイナリ
prime1: 3288743189 (0xc4063d15) ← 素数
prime2: 3285521957 (0xc3d51625) ← 素数
exponent1: 1483866153 (0x58720029)
exponent2: 736092877 (0x2bdfe2cd)
coefficient: 1823248574 (0x6cac90be)

今回作成した秘密鍵 private.pem は当然ながら攻撃者からは見えないものとします。

公開鍵の作成

$ openssl rsa -in private.pem -pubout > public.pem
writing RSA key

$ cat public.pem 
-----BEGIN PUBLIC KEY-----
MCQwDQYJKoZIhvcNAQEBBQADEwAwEAIJAJXz6qyvn6IJAgMBAAE=
-----END PUBLIC KEY-----

$ openssl rsa -noout -text -inform PEM -in public.pem -pubin
Public-Key: (64 bit)
Modulus: 10805237958393700873 (0x95f3eaacaf9fa209) ← 素数の積
Exponent: 65537 (0x10001)

公開鍵 public.pem は一般に公開されるものとします。

攻撃者のターン

攻撃者は公開されている公開鍵 public.pem から秘密鍵の割り出しを試行することにします。

計算用モジュールの導入

後々必要になるので Python の各種計算モジュールを導入しておきます。

# yum -y install python-pip
# yum -y install python-devel
# pip install --upgrade pip  
# pip install sympy
# pip install gmpy

Modulus (素数の積) の取得

公開鍵 public.pem から Modulus (素数の積) を取得します。

$ openssl rsa -noout -text -inform PEM -in public.pem -pubin
Public-Key: (64 bit)
Modulus: 10805237958393700873 (0x95f3eaacaf9fa209) ← 素数の積
Exponent: 65537 (0x10001) ← これもあとで使います

素因数分解

素数の積 Modulus = 10805237958393700873 (0x95f3eaacaf9fa209) が分かったので、これを素因数分解します。
通常、長い鍵であればものすごい大きな Modulus になっているので、そういう大きな数値の素因数分解は（マシンパワー的に）かなり難しいのですが、今回は鍵が短いため、Modulus もお手頃なサイズになっています。

導入済みの Python モジュールを用いて素因数分解を行います。

$ python
>>> import sympy
>>> sympy.factorint(10805237958393700873)
{3288743189: 1, 3285521957: 1}

1秒程で解が求まりました。Modulus 10805237958393700873 は、素数 3288743189 と 素数 3285521957 の積であることがわかりました。

秘密鍵構築用の設定ファイルを作成

以下のようなテキストファイルを作ります。ファイル名は何でも良いですが asn1parse.txt という名前にしておきます。

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:10805237958393700873 … public.pem 内 Modulus の値
pubExp=INTEGER:65537 … public.pem 内 Exponentの値
privExp=INTEGER:?    … あとで計算
p=INTEGER:3288743189 … さきほど求まった素数その1
q=INTEGER:3285521957 … さきほど求まった素数その2
e1=INTEGER:?         … あとで計算
e2=INTEGER:?         … あとで計算
coeff=INTEGER:?      … あとで計算

このテキストファイルを元に秘密鍵を生成（不正に復元）します。

「あとで計算」のところは以下のように計算するルールになっています。

  • privExp = pubExp^–1 mod (p - 1)(q - 1)
  • e1 = privExp mod (p - 1)
  • e2 = privExp mod (q - 1)
  • coeff = q^-1 mod p

Python スクリプトでさくさく計算していきましょう。

$ python
>>> p = 3288743189 
>>> q = 3285521957
>>> pubExp = 65537
>>> import gmpy
>>> privExp = gmpy.invert(pubExp, (p-1)*(q-1))
>>> privExp
mpz(1041168769790190833) … ★ privExp 確定
>>> e1 = privExp % (p - 1)
>>> e1
mpz(1483866153) … ★ e1 確定
>>> e2 = privExp % (q - 1)
>>> e2
mpz(736092877) … ★ e2 確定
>>> coeff = pow(q, p - 2, p)
>>> coeff
1823248574L … ★ coeff 確定

※mod の計算の置き換えはけっこうやっかいなので、そのまま mod 計算したい人は http://www.wolframalpha.com/ を使うのがお勧めです。例えばここに「65537^-1 mod (3288743189 - 1)(3285521957 - 1)」のように打ち込めば privExp の値が求まります。


上記で確定した値を埋めてできあがった asn1parse.txt は以下のような内容になります。

asn1=SEQUENCE:rsa_key

[rsa_key]
version=INTEGER:0
modulus=INTEGER:10805237958393700873
pubExp=INTEGER:65537
privExp=INTEGER:1041168769790190833
p=INTEGER:3288743189
q=INTEGER:3285521957
e1=INTEGER:1483866153
e2=INTEGER:736092877
coeff=INTEGER:1823248574

秘密鍵を（不正に）生成

上で作った asn1parse.txt を元に秘密鍵を（不正に）生成します。

$ openssl asn1parse -genconf asn1parse.txt -out private2.key
    0:d=0  hl=2 l=  61 cons: SEQUENCE          
    2:d=1  hl=2 l=   1 prim: INTEGER           :00
    5:d=1  hl=2 l=   9 prim: INTEGER           :95F3EAACAF9FA209
   16:d=1  hl=2 l=   3 prim: INTEGER           :010001
   21:d=1  hl=2 l=   8 prim: INTEGER           :0E72F97AD29324F1
   31:d=1  hl=2 l=   5 prim: INTEGER           :C4063D15
   38:d=1  hl=2 l=   5 prim: INTEGER           :C3D51625
   45:d=1  hl=2 l=   4 prim: INTEGER           :58720029
   51:d=1  hl=2 l=   4 prim: INTEGER           :2BDFE2CD
   57:d=1  hl=2 l=   4 prim: INTEGER           :6CAC90BE

$ cat private2.key
0=      ꬯     r%Xr)+

private2.key というバイナリの秘密鍵ができました。

中身がバイナリで元の秘密鍵と比較しにくいので pem 形式に変換します。

$ openssl rsa -inform der -in private2.key -outform pem -out private2.pem
writing RSA key


元の秘密鍵 private.pem と、今回不正に作成した秘密鍵 private2.pem を比較してみます。

$ diff private.pem private2.pem --side-by-side -W 80
-----BEGIN RSA PRIVATE KEY-----         -----BEGIN RSA PRIVATE KEY-----
MD0CAQACCQCV8+qsr5+iCQIDAQABAggOcvl60   MD0CAQACCQCV8+qsr5+iCQIDAQABAggOcvl60
cgApAgQr3+LNAgRsrJC+                    cgApAgQr3+LNAgRsrJC+
-----END RSA PRIVATE KEY-----           -----END RSA PRIVATE KEY-----

まったく差分が無いことが確認できました。攻撃者による秘密鍵の復元は成功しました。

おしまい

基本的に秘密鍵は誰にも見せないもの、公開鍵は名前のとおり公開しておくもの、という位置づけですが、鍵の長さが短すぎると今回のように公開鍵から秘密鍵の復元ができてしまいます。

くれぐれも鍵長にはお気を付けを。
（今現在は 2048ビット程度で十分かと思いますがマシンスペックやアルゴリズムの進化によって、もう少し長めのビット数が必要になる時代も遠くないでしょう）

参考

});