残響を追って

writeup&diary

CryptoHack RSA : RSA Starter 1

 

 最初にRSAの簡単な解説が入っている。

 

解説


 RSAは1977年に初めて提案された、最も有名な公開鍵暗号システムである。

 RSAは主に以下の二つの用途で使用される。

 

公開鍵暗号による暗号化

 ユーザであるアリスが公開鍵を配布し、他の誰でもその公開鍵を用いて、メッセージを暗号化してアリスに送信することができる。秘密鍵をもつアリスだけがメッセージを復号できる。

 

・デジタル署名

 アリスは自分の秘密鍵を用いてメッセージにデジタル署名を施すことができる。誰でもアリスの公開鍵を使ってアリスの署名を確認し、メッセージが改ざんされていないことを証明できる。


 RSA暗号の安全性は巨大な合成数因数分解が困難であることを利用しているが、近年RSA暗号は誤った(脆弱性をもつ)実装が容易であると批判されている。

 広く公開されている実装の中でいくつか重大な脆弱性が発見されているが、最も悪名高いのはROCA*1に関する脆弱性で、このせいでエストニアでは76万枚の国民IDカードが停止するはめになった。


 以下の問題では、RSA暗号における多くの重大な誤り(=footgun)を紹介する。現実世界で何百万ドルもの損害をもたらした攻撃の数々を目の当たりにできるだろう。


RSA Starter 1

問題文

 RSAの全ての操作にはべき剰余が含まれる。

 べき剰余は暗号理論において広く使われている演算で、通常は2^10 mod 17 のように表記される。

 これは、ある数をある乗(2^10=1024)まで計算した後、他の数値で除算した残りをとる(1024 mod 17 = 4)と考えることができる。

 Pythonにはこの操作を行うための組み込み関数pow()があり、pow(基数, 指数, 法(モジュラス))を引数にとる。

 RSAでは、このべき剰余と素因数分解を組み合わせることで『落とし戸関数』を構築することができる。この落とし戸関数とは、ある方向には簡単に計算できるが、正しい情報を持っていないと逆に計算することは難しい関数のことを指す。この性質を利用することで、RSA暗号ではメッセージを暗号化することができ、鍵をもっている人だけが逆の操作をしてメッセージを復号することができる。

 では、101^17 mod 22663 の解を計算してみよう。


解説と解答

*1:The Return of Coppersmith's Attackの略。2017年10月、チェコのMasaryk大学の研究チームによってInfineon Technologies AG製のRSA鍵生成モジュールに実装上の脆弱性があることが報告された。このモジュールで生成される素数には制約があり、それが原因で鍵空間が大幅に狭まってしまうために、現行の鍵サイズ(2048bits)に対して現実的な時間およびコストで公開鍵の素因数分解が可能であった。このことから、速やかに対策が取られた。参考→https://www.iij.ad.jp/dev/report/iir/039/02.html

続きを読む