E
Note: P>Q
ChonkyE.txt
ChonkyE.txtを読むと、RSA暗号のeとnが以下のように与えられている。
e = 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
n = 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
このpとqでSchmidt-Samoa暗号化を行ったメッセージも与えられている。
nの素因数分解は難しそうだが、eが大きいためWiener's Attackが行えそうだ。
wa.pyで行う。
# -*- coding: utf-8 -*-
# https://yocchin.hatenablog.com/entry/2017/03/05/192000より
from fractions import Fraction
def continued_fractions(n,e):
cf = [0]
while e != 0:
cf.append(int(n/e))
N = n
n = e
e = N%e
return cf
def calcKD(cf):
kd = list()
for i in range(1,len(cf)+1):
tmp = Fraction(0)
for j in cf[1:i][::-1]:
tmp = 1/(tmp+j)
kd.append((tmp.numerator,tmp.denominator))
return kd
def int_sqrt(n):
def f(prev):
while True:
m = (prev + n/prev)/2
if m >= prev:
return prev
prev = m
return f(n)
def calcPQ(a,b):
if a*a < 4*b or a < 0:
return None
c = int_sqrt(a*a-4*b)
p = (a + c) /2
q = (a - c) /2
if p + q == a and p * q == b:
return (p,q)
else:
return None
def wiener(n,e):
kd = calcKD(continued_fractions(n,e))
for (k,d) in kd:
if k == 0:
continue
if (e*d-1) % k != 0:
continue
phin = (e*d-1) / k
if phin >= n:
continue
ans = calcPQ(n-phin+1,n)
if ans is None:
continue
return (ans[0],ans[1])
e = 91043118409828550796773745518585981151180206101005135117565865602978722878478494447048783557571813980525643725323377488249838860897784683927029906188947001149632101513367258267329961684034661252866484981926055087386190015432964608927947646476193251820354738640453947833718397360834701566765504916472450194494897616371452996381159817427887623703639133290358520498419049175941584678802701606995099241245926884172985004839801270005583030514286561971825047719421487004569752638468907609110285739083279629747310953086535889932550905065172805818862336335628248528993024112446002398466115161473573451161053837400091893285717
n = 156749047558583013960513267351769479915110440411448078412590565797031533622509813352093119636835511977253033854388466854142753776146092587825440445182008237325262012698034419137157047927918635897378973846177552961727126115560551970797370239385129543828686170774323306933202481728884019420422360360849592983818405154473369790181636472137741865440233383956571081122982223602667853668754338360008279002325576495573847568301584365514417593244726435632222027817410359417329310347952169273512510934251453361933794586716533950489973436393834189505450956622286216819440777162804798432330933357058175885674184582816364542591313
(p,q) = wiener(n,e)
print 'p = ', str(p)
print 'q = ', str(q)$ python2 wa.py
p = 462648222004918001013626929700851985161214529015962355517097297750332107059692278343607439888140451722661722449586909096508950271217838478793469222136256780856060573039970361424138955569021582604733404145398646735820327194382610835536537670219091779958808528053471059443883883244638910795974245528935198178697
q = 338808278305491368568107597536870102903517054340801660200304926784154444523223906451699772927968482815828890482348342203845897909840260655384526983598744312581591533978845446602589686620835190303243711955190856932946979670202446096542521271004217036632261094082852110229243380763789393081471800046961479400329素数pとq(p>q)がわかったため、メッセージを復号できる。
以下のssdec.pyで行う。
from Crypto.Util.number import *
p = 462648222004918001013626929700851985161214529015962355517097297750332107059692278343607439888140451722661722449586909096508950271217838478793469222136256780856060573039970361424138955569021582604733404145398646735820327194382610835536537670219091779958808528053471059443883883244638910795974245528935198178697
q = 338808278305491368568107597536870102903517054340801660200304926784154444523223906451699772927968482815828890482348342203845897909840260655384526983598744312581591533978845446602589686620835190303243711955190856932946979670202446096542521271004217036632261094082852110229243380763789393081471800046961479400329
c = 16267540901004879123859424672087486188548628828063789528428674467464407443871599865993337555869530486241139138650641838377419734897801380883629894166353225288006148210453677023750688175192317241440457768788267270422857060534261674538755743244831152470995124962736526978165448560149498403762447372653982922113772190234143253450918953235222315161964539311032659628670417496174123483045439359846360048774164337257829398345686635091862306204455687347443958931441225500856408331795261329035072585605404416473987280037959184981453888701567175803979981461050532113072292714696752692872526424122826696681194705563391161137426703690900733706866842363055967856443765215723398555522126909749236759332964873221973970368877565410624895160438695006432021529071866881905134494489266801004903504121740435965696128048690741210812963902631391765192187570107372453917327060678806282122942318369245760773848604249664378721970318257356486696764545
n = p*p*q
key = inverse(n, (p-1)*(q-1))
pq = GCD(pow(2, n*key, n)-2, n)
print(long_to_bytes(pow(c, key, pq)))$ python ssdec.py
b'flag{remarkably_superb_acronym}'flagが出てきた。