はじめに
この記事は弊研究室の某課題について考える21日目の記事です。
前回RSAの暗号についてやったので今回はRSAの危ない運用に関して話します
公開鍵Nのビット数が短いとまずい
公開鍵Nのビット数が短いと普通に計算して素数を求められます。そうするとpとqがわかってしまうのでまずいということで今回は短いビット数の鍵を復号します。
Pollard-Rhoアルゴリズム + Miller-Rabin素数判定法を用いて素数を見つけます。素数となる数でどんどん割っていく方法だと時間がかかるのでしょっぱなからこれでいきます。
import sys
from random import randint
from fractions import gcd
from Crypto.PublicKey import RSA
def miller_rabin(n,k=20):
s, d = 0 , n-1
while d % 2 == 0:
s+=1
d/=2
for i in range(k):
a = randint(2,n-1)
y = pow(a,d,n)
if y == 1:
continue
for j in range(s):
if y == n-1:
break
y = (y*y) %n
else:
return False
return True
def pollard_rho(n, c=1):
x, y, d = 2, 2, 1
while d == 1:
x = (x*x + c) % n
y = (y*y + c) % n
y = (y*y + c) % n
d = gcd(abs(x-y),n)
if d != n:
return d
#N = 821 * 953
key = RSA.importKey(open("96key.pem").read())
print key.n
print pollard_rho(key.n)
$ time python pollard_rho.py
67347099272184651187705110721
239973115325831
real 2m25.078s
user 2m25.004s
sys 0m0.017s
こんな感じで素因数分解の答えを出してきます。意外と時間がかかるので自分の計算機でどこまでの鍵なら計算できるのか知っておくと便利かも。自分は128の鍵は30分以上かかりました。
素数pとqの値が近いとまずい
選んだ素数pとqの値が近いとフェルマー法によって求められます。
Fermat法は素数同士の積からなる合成数において、二つの素数の差が小さい場合に有効なアルゴリズムである。 具体的には、合成数nの平方根周辺のある値をxとしたとき、(x-k)*(x+k) == nとなるkを小さいものから求める。
p*qの積のNがあった際にNより大きい
を考え
とあらわすことができれば、a+bとa-bが素因数分解の結果となるということです。
まぁ書きます。手順としてはNに近い平方根を計算すること。そしてそれに近いbを試していくことって感じ。まぁbを試すためにはxを増やしたりyを増やしたりって感じで試していく
def isqrt(n):
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n//x) //2
return x
def fermat(n):
x = isqrt(n) + 1
y = isqrt(x * x - n)
while True:
w = x * x - n - y * y
if w == 0:
break
elif w > 0:
y += 1
else:
x += 1
return x+y, x-y
n = 0x86E996013E77C41699000E0941D480C046B2F71A4F95B350AC1A4D426372923D8A4561D96FBFB0240595907201AD3225CF6EDED7DE02D91C386FFAC280B72D0F95CAE71F42EBE0D3EDAEACE7CEA3195FA32C1C6080D90EF853D06DD4572C92B9F8310BBC0C635A5E26952511751030A6590816554E763031BCBB31E3F119C65F
p,q = fermat(n)
print p
print q
実行結果は下のように
$ time python fermat.py
9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987246769
9733382803370256893136109840971590971460094779242334919432347801491641617443615856221168611138933576118196795282443503609663168324106758595642231987245583
real 0m0.015s
user 0m0.007s
sys 0m0.008s
複数のRSA暗号があるとき同じ素数を使っているとまずい
つい最近のCTF問題でもありましたね。Common's factors attackと言われるものです。
これですが複数のRSA公開鍵のNから最大公約数を求めればいいです。問題を用意するのが大変なので今回はとある問題から素数を合成数をいただきます
用意する問題は当然ps and qsです。
今年のsecconの問題ですね。私も解いたんですがその時にはBKPのやつを借りました。今回は時間に余裕があったので一からコード組みますっていっても公約数求めるだけなのでたいしたことはない
from Crypto.PublicKey import RSA
from fractions import gcd
import gmpy
E = 65537
def common_factor(N1, N2):
p = gcd(N1,N2)
return (p, N1/p), (p,N2,p)
def form_priv_key(n,p,q):
phi = (p-1) * (q-1)
d = gmpy.invert(E,phi)
key = RSA.construct((long(n),long(E),long(d),long(p),long(q)))
return key
key1 = RSA.importKey(open("pub1.pub").read())
key2 = RSA.importKey(open("pub2.pub").read())
print key1.n
print key2.n
privkey1, privkey2 = common_factor(key1.n,key2.n)
privkey = form_priv_key(key1.n, privkey1[0], privkey1[1])
print privkey.decrypt(open("cipher").read())
privkey = form_priv_key(key2.n, privkey2[0], privkey2[1])
print privkey.decrypt(open("cipher").read())
結果はこんな感じ。
$ python2 common_factor.py
847796795638781450678718708664542960446354226336422534142899480441478781747168340722544245493739168125415291376063352480076469305992008517388366298914970810765149321160596112226917023146371080685458239747986992197343482255681414590678694753885521068656675164266739274608505094927725285868801825144058835115051061857233824816176186349372737400492228548130718029270482313906040935333159681273527671359469173939861889228505791626525994180917670701909816457560622922219797109618405842358250940062127841301193206255543580550667149741357342408703680375118252445296600962244008043713708516004025217199954286478272550961283413053789743740774140439284662596273452124779590753836094450154459078034659421366584354005421566290862244000178569163732971816333961711759000171156293724203334889496589376907683142167883476184246287660764821622298961378903818077158234683927321823293466245584486980446609569799420950073036635602004293246754252079757527610246223280774592566063422181158810677919909523144033543195999214800559998598003329294711989868113423468536273984117507008756542731210465222475943122324672467669623079721727526348599823126409108190030551584092950358235465140166515452377475799157617227362838246912839086733412861436353117994501342653
763718912475160487902804749669814117361530270298225094625871588939939773892509348006077810445741086683427253000695920011673348476297973798322806091336777405584801442639626925406721932533140226556519019440300864340670199686368307155860493615065198319490060598587202051942638792919648596288576294804549738135969737494734307362891313864027749187674251692407867312885251279302785352318725391842117065840058358065676707016006124478822206302825992616559261930620693061673348139416033418864269248381876692676529410115745518353146254670349865568255213560376368953292931958006941630719304442332912813624543600126197554727832190226632919876204677667384620275620336951964833888599634720101911051166398907898747710391394105753614253527704990658698844796442515669670816004761855554187277637871343595647487793209271354240148469085627742503649786300484610102224828274384484809539697728008552925590472129497180290668277790132130824141651399551803499770513576176720509094833332201946177880267399933460994496277590932311628302240154240967341858152145815276163397709272690500041597393678630136932574450837982593210399370333578887450410911663220219423601973078501237709613593311133945501455828164291429228495931943107997137587307522565029820756690578833
▒H4؋ѝ2l▒r
▒puF`u▒▒▒3▒4CT▒R
▒▒V▒Z[]▒▒▒▒%▒▒)() _▒d▒
|▒o▒h▒o▒V▒▒s{t_▒vӫ▒1ۧ▒[:▒X▒Y▒▒%▒%▒▒r▒9dJ▒|▒▒▒▒▒▒▒7▒▒M▒▒
g▒B▒▒▒▒݁t^Scq▒`H▒0▒c▒f▒▒▒▒Ŏ\▒
6▒a ▒▒"5`▒_▒et:
▒▒a▒C =▒L▒X▒ UmL▒b▒'▒▒▒\▒X▒▒▒3▒▒l>▒▒(W!▒▒T▒▒▒▒e▒DǷ.▒▒?f▒L.▒U▒▒▒▒▒▒nR~J▒.▒'▒&/▒▒w▒▒▒▒!A▒wS"U▒▒Z▒*▒ ▒▒▒E▒T▒d▒w▒@▒J!▒=▒▒▒▒"▒▒,▒▒▒▒Dh▒▒▒▒▒▒ ▒▒▒▒(▒l▒▒▒4UayXg4Ї4Z▒Z▒▒Ma▒▒5▒▒▒|▒ۻ▒;Z▒-S▒@▒▒]> \n6>▒g▒MBK▒▒E▒@▒a▒VYԹB▒p▒▒▒`▒[▒53▒1▒],▒GA".▒
▒▒5▒摨SECCON{1234567890ABCDEF}
▒▒C@▒▒&▒▒▒▒▒▒?▒w▒▒▒9▒y▒N>▒g▒▒▒A▒n▒<Sy▒▒▒▒▒▒▒ڍ▒▒E▒T▒8T▒▒X▒ލ▒O>ƾ▒H▒▒▒`▒=▒
▒▒R▒▒▒▒0
ƞ▒R▒8Η▒\o"▒▒Kf+8▒▒5o▒V▒=
▒E▒▒▒▒yv▒▒C▒>▒▒Όme[▒▒e
▒螉\MNu4z▒▒▒}▒▒▒4 ▒Gf▒Ȯ▒▒▒▒▒P▒▒▒"K▒▒Ќ>▒aW▒▒▒)4▒C▒ϿK▒▒▒T▒0▒/▒B▒T▒]YL@-▒▒▒▒ ▒e▒*▒Ҟ▒ӥ▒▒▒▒▒▒}▒֫▒DŢ<R%Ƙ▒Z▒<▒y[▒PI▒▒T▒e1▒▒▒l▒T▒p.▒▒▒t[▒ko▒$▒G▒▒▒~i▒▒▒▒▒▒▒▒$▒▒▒:Z|▒▒u▒c▒▒▒0▒k▒OBO▒kZ▒CV▒▒6▒▒▒▒▒ $>▒ԃBf▒V▒f▒▒▒.<o▒▒▒▒Q~▒j▒▒`j
終わり
まだまだ危ない運用はあるのですがひとまずはこんな感じでよいでしょう。私の勉強のためにもここらへんはまとめておきたいものですね
参考文献
