크립토 RSA 문제 풀이(낮은 지수 공격, d값 계산)

easy_e

My mistake is small e..
N = 17833815166674215561144380229561602179923731799132788419555594954367442029455089418743399809217145437300408789915420084645818032797703304401530612721747894060231753572199355173876590923106237833227739227018047803439827258075925645601976809131259089808893982863646247510075221280008122394372628937027150779301518996963848669458923437657864087288796091424334791084225212550519333808533533327431105536281629980398084648705899351608932999676671059854514719184802159884320916115598375367684648649304258821908333243169451163070517695399551502288634977120729612820361152561298644541378376202743662938052785591888132625312181
c = 2523454692080985130926824733361219117105925267704273748310491104599011343499491160640561478562668718117804355694949
e = 3

너무 작은 e가 주어진 문제

 

이렇게 너무 작은 e값과 너무 큰 n값이 같이 주어졌을 때 가능한 공격에 낮은 지수 공격이 있다

보통 이런 경우 e값은 3을 주는데, 암호문의 세제곱근을 구하면 평문이 된다

gmpy2의 iroot나 cbrt를 사용하여 풀 수 있다

m = iroot(c, 3)[0]
m = cbrt(c)

cbrt는 세제곱근을 구해주고, iroot는 두 번째 인자를 3으로 주면 세제곱근을 구해준다

주의할 점은 iroot는 반환값이 튜플이라 0번째 있는 값이 원하는 값이다

 

from gmpy2 import *

c = 2523454692080985130926824733361219117105925267704273748310491104599011343499491160640561478562668718117804355694949

with local_context() as ctx:
    ctx.precision = 3000
    m = cbrt(c)
    #m = iroot(c, 3)[0]
    
    print ('%x' % int(m)).decode("hex")

혹은

from gmpy2 import *

c = 2523454692080985130926824733361219117105925267704273748310491104599011343499491160640561478562668718117804355694949

ctx = get_context()
ctx.precision = 3000
m = cbrt(c)
#m = iroot(c, 3)[0]
    
print ('%x' % int(m)).decode("hex")

gmpy2의 get_context()는 산술 동작을 제어하는 데 사용한다 (gmpy2.readthedocs.io/en/latest/mpfr.html )

get_context()는 정밀도 제어나 반올림 모드를 제어할 수 있고, 최소 및 최대 지수값을 변경하거나, 예외 처리, 오버/언더플로우 등의 기능 등이 있다

ctx=get_context()를 하면 모든 옵션이 기본값으로 된 새 컨텍스트를 만든다

 

여기서 사용한 것은 precision으로, 정밀도에 관한 값이다

결과 값이 제대로 나오지 않는다면 더 높게 설정해서 정밀도를 올릴 수 있다

 

---

myPrivatekey

My Private key leaked~
phi = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733855850563121229212919614870629815706079606220871508903841727402814339384578549212124030181289268556255605556462262215034668423236882520695239627559904020281499927979831389029969019829095252031822779012678507402377916410144606589983681845721957381827624407936397476592806471370644374868522766022819870197111204440
n = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733856156811192771870602856568816330053155412189330149287658917220084117422477737432709948576788031260905005742860826571594847937212100950533703614841755154052910734542215287496941210843206017137581508016542011903277402767402219140077313852775334164577572703553955826477449270131749844530868444193626077136684359727
c = 17690551262096405896997154248725997515162859536189985259882620957841740356071423219560297369474828213466967201771164687541608745959958467063622022419843151428220248429311985180109113409296866627645017481648436647470073637057339226996155027170872942948923904302506711076655585890415141797781507177399516687651493521523703286733762563735525517513570518486400810504153999312891688387831723168627964370935160294311101923119713980141096689780888538850330510146325767650622448208609031278489950532189695427650410320398942689734345440267920479954877726527607076209770130773170212954092147635827833024203399183409626583390820
e = 65537

RSA에서 n값과 phi값을 계산할 수 있으면 d값이 나와서 복호화가 가능하다

아니면 p, q, e값이 주어졌을 때도 n과 phi값을 계산할 수 있다

만약 p, q, e가 주어졌으면 n = p*q로 n 구하고, phi=(p-1)*(q-1)로 phi를 구하면 된다

 

n과 phi값을 구했으면 d를 구하기 위해 mod n에 대한 곱셈의 역원(곱했을 때 1이 나오는 수)을 구한다

곱셈의 역원은 gmpy2의 invert나 divm으로 계산할 수 있다

 

d = invert(e, phi)
d = divm(1, e, phi)

invert는 바로 곱셈의 역원을 구해주고, divm는 첫 번째 인자를 1로 지정해주면 역원을 구해준다

 

from gmpy2 import *

phi = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733855850563121229212919614870629815706079606220871508903841727402814339384578549212124030181289268556255605556462262215034668423236882520695239627559904020281499927979831389029969019829095252031822779012678507402377916410144606589983681845721957381827624407936397476592806471370644374868522766022819870197111204440
c = 17690551262096405896997154248725997515162859536189985259882620957841740356071423219560297369474828213466967201771164687541608745959958467063622022419843151428220248429311985180109113409296866627645017481648436647470073637057339226996155027170872942948923904302506711076655585890415141797781507177399516687651493521523703286733762563735525517513570518486400810504153999312891688387831723168627964370935160294311101923119713980141096689780888538850330510146325767650622448208609031278489950532189695427650410320398942689734345440267920479954877726527607076209770130773170212954092147635827833024203399183409626583390820
n = 23079175999650261543000051288341715950034109926658542519727080390553485584836589385804681319018295730173751924209320558260485473378546413216108872802506593333079135314669197743332337508879842413221472886943211445491722723443429004123868556481781431711563268181969712877598553629448215935461900433200909733856156811192771870602856568816330053155412189330149287658917220084117422477737432709948576788031260905005742860826571594847937212100950533703614841755154052910734542215287496941210843206017137581508016542011903277402767402219140077313852775334164577572703553955826477449270131749844530868444193626077136684359727
e = 65537

d = invert(e, phi)

print ('%x' % pow(c, d, n)).decode("hex")

phi, c, n, e값을 넣어주고 d값을 구한다

다 구했으면 c의 d승을 n으로 나눈 나머지(pow)로 나온 hex값을 디코딩 해 주면 된다