様々なところで利用される暗号化方式の RSA であるが、OMSCS で受講した Introduction to Information Security (IIS) の Cryptography に関する課題では、RSA の脆弱性に関して知ることができた。RSA の原理を含めて学んだことを整理したいと思う。
RSA Overall
RSA 暗号は公開暗号方式に分類される暗号化方式であり、TLS や SSH にも利用されている。 公開暗号方式であるため暗号鍵と復号鍵が別であり、暗号鍵は公開されている。 具体的には、二つの異なる素数 p, q を選択し、N=pq とする。 これに対して、(p-1) x (q-1) と互いに素となる自然数 e を選択する。 加えて、(p-1) x (q-1) で割ったときに、余りが 1 となる ed を構成するように自然数 d を選択する。
ここで、暗号化する際には、暗号化したいメッセージを m とした場合、暗号 c は以下のように算出可能である。
復号化する際には、以下の計算になる。
そのため、送信者がメッセージを暗号化して送る場合は、公開鍵である N, e を利用して暗号化する。一方、暗号化されたメッセージの復元には d が必要であるが、p, q, d は公開されない秘密鍵であるため、これらを知っている場合にしか復号化できない。
RSA暗号とは？仕組みや応用事例を初心者にもわかりやすく解説！
拡張ユークリッドの互除法
課題を解く際に、ユークリッドの互除法、拡張ユークリッドの互除法を利用した。完全には理解できていない部分もあるが、自分が学んだに関して整理しておく。 ユークリッドの互除法に関しては、二つの自然数の最大公約数 (gcd) を求める方法の一つであり、大きな自然数の最大公約数を求める際に効率的に算出が可能である。 暗号に利用される値は容易に計算できないよう大きな値が利用されるため、ユークリッドの互除法が有効である。
また、拡張ユークリッドの互除法では、以下を満たす (x, y) を求める。
ここで RSA の定義から、e と (p-1) x (q-1) は互いに素である。 l = (p-1) x (q-1) とすると、gcd(e, l) = 1 となる。 よって上記の式は以下のようになり、これを満たす x が d となる。
拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜
Vulnerabilities
上記の通り、第三者が復号化を試みる際には d の算出が必要であるが、d を求めるためには p, q を知る必要がある。N は公開されているため、N の素因数分解によって p, q が得られるが、大きな N の素因数分解には時間を要するため、読み取るのは容易ではないという特性がある。
しかしながら、状況によっては RSA 暗号における脆弱性を利用することで、p, q, d もしくは m 自体を第三者が取得する方法は以下のようにいくつか存在する。
Weak Key Attack
複数の N を生成する際に、同じ乱数生成器を利用するなどで、p, q を共有するような場合に存在する脆弱性である。この状況だと、p もしくは q を取得することができ、最終的に復号化することが可能である。 以下の論文では、インターネット上に存在する大量の N を計算することで、同じような乱数生成器を利用している N に対する脆弱性を見つけたことを指摘している。
Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices
具体的な計算方法に関しては、各 N の積で表される Product Tree を算出し、それの余りを求めた Remainder Tree から、各 N との最大公約数を求めている。 この最大公約数が 1 でない場合に、p, q を計算することができる。
Fast Bulk GCD Implementation in Go to Detect Shared Primes in RSA Keys
実装に関しては、こちらのサイトも参考になったと思う。
Broadcast Attack
N は異なるものの同じメッセージを小さい e を用いて暗号化した際に、メッセージを算出することができてしまうという攻撃である。 中国剰余定理を利用することで、メッセージを計算可能であり、その際の実装は以下を参照した。 また、a, m をうまく定義することがコツのように見受けられる。
Parity Oracle Attack
LSB Oracle Attack とも言われる攻撃である。少々現実的なシナリオではないが、暗号文を復元した際の最下位の 1 bit Least Significant Bit (LSB) はわかる場合に、平文を求めることができるという攻撃である。こちらのブログに詳細が案内されている。
Practical Padding Oracle Attacks on RSA
Reflection
IIS の中では数学の要素が強い課題であり、受講者の点数が低い傾向にあることが示されていた。確かにそれぞれの脆弱性に関する数式を展開していき、理論を追っていくことにはかなりの時間を要した。 しかし、RSA に関しては意識しないところで日常的に利用しているため、この機会に理論を学ぶことができ多くの発見があった。公開鍵における何が公開されており何が秘密なのかに関して、具体的に理解することができたと思う。