IN CTF,Rsa often appears.BUT in ctf it’s usually with Fixed method to solve it.
Today,I put all code to here.
1.have p,q,e.compute d or p,q,e,c to decrypte ciphertext
you should note that e should be a prime number
def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
#y maybe < 0, so convert it
if y < 0:
return fn + y
return y
def extendedGCD(a, b):
#a*xi + b*yi = ri
if b == 0:
return (1, 0, a)
#a*x1 + b*y1 = a
x1 = 1
y1 = 0
#a*x2 + b*y2 = b
x2 = 0
y2 = 1
while b != 0:
q = a / b
#ri = r(i-2) % r(i-1)
r = a % b
a = b
b = r
#xi = x(i-2) - q*x(i-1)
x = x1 - q*x2
x1 = x2
x2 = x
#yi = y(i-2) - q*y(i-1)
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)
c=174351854900966188977904987134427781775272319015132758864873306597577750098226384697676493069934493337172878644704026414143158278061735487156753876228693871133246943987986736376334978394288726798629969739682159093341216933569685433834399066431572596217448890045449452777575588109633903180187737151526697202981068022052927269776042366636567373169048897053407525377739061532954622334926090886616814795353343617608514882733311276797401041432521552887309768062119475432313577704285175154999953744808693060762751860890138121483113217037477525088532442342551435801844941921381421754649633057679452893025326942215634059805893
e=65537
p=7
n=327686759455107101770244900847669909444589048412360834576685246062688127536081099083429267251807434658755027942434088691531411358608813564103474260906760890856572316124720411994944452029909143528618601332276557030331449922914588098651910546381598167047448472663466757577538599646576321101391165156123505615545132362901633176715824845507656500702749953003718520197296421627262166996961876028666789909011002781946123522101211391085819205716356811390841768572223338428099889208616922338336413929957447204562949543074397015746616534379026758490398097163404992258919511999330535101502534548628286576966950951725386015104827
q=n/7
fn=(p - 1) * (q - 1)
d = computeD(fn, e)
print(d)
m = pow(c, d, n)
print(hex(m)[2:-1].decode('hex'))
2. factor N
if n<256bit or n have two close number.yafu and foctordb will be very helpful.
Note:yafu in windows or in linux is not same.you can try both of them.
3. Common Modulus Attack
if use the same n to encrypt the same m. Common Modulus Attack is useful.
# coding=utf-8
import string
import gmpy
def egcd(a, b):
if a == 0:
return b, 0, 1
else:
g, y, x = egcd(b % a, a)
return g, x - b // a * y, y
def main():
c1=3453520592723443935451151545245025864232388871721682326408915024349804062041976702364728660682912396903968193981131553111537349
c2=5672818026816293344070119332536629619457163570036305296869053532293105379690793386019065754465292867769521736414170803238309535
n = 6266565720726907265997241358331585417095726146341989755538017122981360742813498401533594757088796536341941659691259323065631249
e1 = 773
e2 = 839
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
if s1 < 0:
s1 = -s1
c1 = gmpy.invert(c1, n)
elif s2 < 0:
s2 = -s2
c2 = gmpy.invert(c2, n)
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print(m)
print ('try:','{:x}'.format(int(m)).decode('hex'))
q=[102,108,97,103,123,119,104,101,110,119,101,116,104,105,110,107,105,116,105,115,112,111,115,115,105,98,108,101,125]
s=""
for i in q:
s+=chr(int(i))
print(s)
if __name__ == '__main__':
main()
4. Basic Broadcast Attack
use the same e to encrypte the same m.
# coding:utf8
from struct import pack,unpack
import zlib
import gmpy
def my_parse_number(number):
string = "%x" % number
#if len(string) != 64:
# return ""
erg = []
while string != '':
erg = erg + [chr(int(string[:2], 16))]
string = string[2:]
return ''.join(erg)
def extended_gcd(a, b):
x,y = 0, 1
lastx, lasty = 1, 0
while b:
a, (q, b) = b, divmod(a,b)
x, lastx = lastx-q*x, x
y, lasty = lasty-q*y, y
return (lastx, lasty, a)
def chinese_remainder_theorem(items):
N = 1
for a, n in items:
N *= n
result = 0
for a, n in items:
m = N/n
r, s, d = extended_gcd(n, m)
if d != 1:
N=N/n
continue
#raise "Input not pairwise co-prime"
result += a*s*m
return result % N, N
sessions=[{"c": 7366067574741171461722065133242916080495505913663250330082747465383676893970411476550748394841437418105312353971095003424322679616940371123028982189502042, "e": 10, "n": 25162507052339714421839688873734596177751124036723831003300959761137811490715205742941738406548150240861779301784133652165908227917415483137585388986274803},
{"c": 21962825323300469151795920289886886562790942771546858500842179806566435767103803978885148772139305484319688249368999503784441507383476095946258011317951461, "e": 10, "n": 23976859589904419798320812097681858652325473791891232710431997202897819580634937070900625213218095330766877190212418023297341732808839488308551126409983193},
{"c": 6569689420274066957835983390583585286570087619048110141187700584193792695235405077811544355169290382357149374107076406086154103351897890793598997687053983, "e": 10, "n": 18503782836858540043974558035601654610948915505645219820150251062305120148745545906567548650191832090823482852604346478335353784501076761922605361848703623},
{"c": 4508246168044513518452493882713536390636741541551805821790338973797615971271867248584379813114125478195284692695928668946553625483179633266057122967547052, "e": 10, "n": 23383087478545512218713157932934746110721706819077423418060220083657713428503582801909807142802647367994289775015595100541168367083097506193809451365010723},
{"c": 22966105670291282335588843018244161552764486373117942865966904076191122337435542553276743938817686729554714315494818922753880198945897222422137268427611672, "e": 10, "n": 31775649089861428671057909076144152870796722528112580479442073365053916012507273433028451755436987054722496057749731758475958301164082755003195632005308493},
{"c": 17963313063405045742968136916219838352135561785389534381262979264585397896844470879023686508540355160998533122970239261072020689217153126649390825646712087, "e": 10, "n": 22246342022943432820696190444155665289928378653841172632283227888174495402248633061010615572642126584591103750338919213945646074833823905521643025879053949},
{"c": 1652417534709029450380570653973705320986117679597563873022683140800507482560482948310131540948227797045505390333146191586749269249548168247316404074014639, "e": 10, "n": 25395461142670631268156106136028325744393358436617528677967249347353524924655001151849544022201772500033280822372661344352607434738696051779095736547813043},
{"c": 15585771734488351039456631394040497759568679429510619219766191780807675361741859290490732451112648776648126779759368428205194684721516497026290981786239352, "e": 10, "n": 32056508892744184901289413287728039891303832311548608141088227876326753674154124775132776928481935378184756756785107540781632570295330486738268173167809047},
{"c": 8965123421637694050044216844523379163347478029124815032832813225050732558524239660648746284884140746788823681886010577342254841014594570067467905682359797, "e": 10, "n": 52849766269541827474228189428820648574162539595985395992261649809907435742263020551050064268890333392877173572811691599841253150460219986817964461970736553},
{"c": 13560945756543023008529388108446940847137853038437095244573035888531288577370829065666320069397898394848484847030321018915638381833935580958342719988978247, "e": 10, "n": 30415984800307578932946399987559088968355638354344823359397204419191241802721772499486615661699080998502439901585573950889047918537906687840725005496238621}]
data = []
for session in sessions:
e=session['e']
n=session['n']
msg=session['c']
data = data + [(msg, n)]
print "-" * 80
print "Please wait, performing CRT"
x, n = chinese_remainder_theorem(data)
e=session['e']
realnum = gmpy.mpz(x).root(e)[0].digits()
print my_parse_number(int(realnum))
tips: usually if e=3,choose 3 groups;if e=10,choose 7 groups.
5.use openssl to decrypte
read public.pem
use openssl
openssl rsa -pubin -in pubkey.pem -text -modulus
or use python
from Crypto.PublicKey import RSA
with open('./pubkey.pem', 'r') as f:
key = RSA.importKey(f)
n = key.n
e = key.e
generate the private.pem
we should use rsatools.py
#!/usr/bin/env python2
import base64, fractions, optparse, random
try:
import gmpy
except ImportError as e:
try:
import gmpy2 as gmpy
except ImportError:
raise e
from pyasn1.codec.der import encoder
from pyasn1.type.univ import *
PEM_TEMPLATE = '-----BEGIN RSA PRIVATE KEY-----\n%s-----END RSA PRIVATE KEY-----\n'
DEFAULT_EXP = 65537
def factor_modulus(n, d, e):
"""
Efficiently recover non-trivial factors of n
See: Handbook of Applied Cryptography
8.2.2 Security of RSA -> (i) Relation to factoring (p.287)
http://www.cacr.math.uwaterloo.ca/hac/
"""
t = (e * d - 1)
s = 0
while True:
quotient, remainder = divmod(t, 2)
if remainder != 0:
break
s += 1
t = quotient
found = False
while not found:
i = 1
a = random.randint(1,n-1)
while i <= s and not found:
c1 = pow(a, pow(2, i-1, n) * t, n)
c2 = pow(a, pow(2, i, n) * t, n)
found = c1 != 1 and c1 != (-1 % n) and c2 == 1
i += 1
p = fractions.gcd(c1-1, n)
q = (n / p)
return p, q
class RSA:
def __init__(self, p=None, q=None, n=None, d=None, e=DEFAULT_EXP):
"""
Initialize RSA instance using primes (p, q)
or modulus and private exponent (n, d)
"""
self.e = e
if p and q:
assert gmpy.is_prime(p), 'p is not prime'
assert gmpy.is_prime(q), 'q is not prime'
self.p = p
self.q = q
elif n and d:
self.p, self.q = factor_modulus(n, d, e)
else:
raise ArgumentError('Either (p, q) or (n, d) must be provided')
self._calc_values()
def _calc_values(self):
self.n = self.p * self.q
if self.p != self.q:
phi = (self.p - 1) * (self.q - 1)
else:
phi = (self.p ** 2) - self.p
self.d = gmpy.invert(self.e, phi)
# CRT-RSA precomputation
self.dP = self.d % (self.p - 1)
self.dQ = self.d % (self.q - 1)
self.qInv = gmpy.invert(self.q, self.p)
def to_pem(self):
"""
Return OpenSSL-compatible PEM encoded key
"""
return (PEM_TEMPLATE % base64.encodestring(self.to_der()).decode()).encode()
def to_der(self):
"""
Return parameters as OpenSSL compatible DER encoded key
"""
seq = Sequence()
for x in [0, self.n, self.e, self.d, self.p, self.q, self.dP, self.dQ, self.qInv]:
seq.setComponentByPosition(len(seq), Integer(x))
return encoder.encode(seq)
def dump(self, verbose):
vars = ['n', 'e', 'd', 'p', 'q']
if verbose:
vars += ['dP', 'dQ', 'qInv']
for v in vars:
self._dumpvar(v)
def _dumpvar(self, var):
val = getattr(self, var)
parts = lambda s, l: '\n'.join([s[i:i+l] for i in range(0, len(s), l)])
if len(str(val)) <= 40:
print('%s = %d (%#x)\n' % (var, val, val))
else:
print('%s =' % var)
print(parts('%x' % val, 80) + '\n')
if __name__ == '__main__':
parser = optparse.OptionParser()
parser.add_option('-p', dest='p', help='prime', type='int')
parser.add_option('-q', dest='q', help='prime', type='int')
parser.add_option('-n', dest='n', help='modulus', type='int')
parser.add_option('-d', dest='d', help='private exponent', type='int')
parser.add_option('-e', dest='e', help='public exponent (default: %d)' % DEFAULT_EXP, type='int', default=DEFAULT_EXP)
parser.add_option('-o', dest='filename', help='output filename')
parser.add_option('-f', dest='format', help='output format (DER, PEM) (default: PEM)', type='choice', choices=['DER', 'PEM'], default='PEM')
parser.add_option('-v', dest='verbose', help='also display CRT-RSA representation', action='store_true', default=False)
try:
(options, args) = parser.parse_args()
if options.p and options.q:
print('Using (p, q) to initialise RSA instance\n')
rsa = RSA(p=options.p, q=options.q, e=options.e)
elif options.n and options.d:
print('Using (n, d) to initialise RSA instance\n')
rsa = RSA(n=options.n, d=options.d, e=options.e)
else:
parser.print_help()
parser.error('Either (p, q) or (n, d) needs to be specified')
rsa.dump(options.verbose)
if options.filename:
print('Saving %s as %s' % (options.format, options.filename))
if options.format == 'PEM':
data = rsa.to_pem()
elif options.format == 'DER':
data = rsa.to_der()
fp = open(options.filename, 'wb')
fp.write(data)
fp.close()
except optparse.OptionValueError as e:
parser.print_help()
parser.error(e.msg)
python rsatools.py -o private.pem -e 65537 -p 285960468890451637935629440372639283459 -q 304008741604601924494328155975272418463
decrypte
openssl rsautl -decrypt -in flag.enc -inkey private.pem
6.robin
e=2,it change to robin encryption.
tips:factor n,and use the python scripts.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from libnum import n2s,s2n
from gmpy2 import invert
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
c1 = 463861008715592544541788096958649982380822291993552963661158341083846355706002434243934700644973050350312929747219220890560457890313935777592023703351727593419636777359461171339858607119280562005428366329387881166391098115609145938874628114686795611562877497053809598457912418305834273787716982828673966892511281860557783258533261018387471625613663795007228658816252387085466650755883925526958541825222104147849869543037051564421185564554779540328456839232497404387290624286751566497788567952632360610202764706896626948910002870580127130312643007535939055701346777869816192299596023048076518131526912498284229673371086451392093044296762919642063285989747843447863750040049168164995180248537696839181948713195802142440769355170646676213720809021239439003677117223691298857042248760498034349423407473670451239334072146014950322552189012974940288556937727948167308597745265347385839657632044783493614334001410069910239130566741665106961136354024810810762895951475543242485783800975807492277070656820419568903493214148024889196426647826970230572261314165620636524851460205285978154492707641609544222797219280033396022038053564505730709726626191701076448925166798629160333223816800919504603549706970069896984937227311709903117484219056513
c2 = 195927128375915404159831782462849519421997168919281192367229155964060692077108973872052067093830637435252224973106403590960932515038799457446882667747435423710065935543543844413331083110324200262663792099201343806708421236272615410153800048782940883675292129942393866266808892179233016046998828763505477208746508926921965388801062981929590402046412505111940482772986190133625714699124188164875578090687811453005795224867122919491454673337692814426115843867664958620407645606387890667138977076727434377908888216522129550500939598401247647451284377783348961677038054513371331912131036588363741320174543932216775500758772806202930724606218837813090150058942140302970078470023234601410850114012056651579503201865188078915561504282163872927300515159998426449361756610452381205386016234990077066797140322333463064165598646284901334076981455665261664866944699135608136052568226611778555151714388687630634120924870097471977570019937467642561549382597187489391364324926276292677979682469604330880184704070172829714637547167378168252389633223108429705879462848460071858533428563787744545008456341542179870964497696809334435217174394915252063444720170993440241479128761827816861630516781632778764274272389367661890340952041792122059256233164391
c2 = invert(c2,n)
e1 = 17
e2 = 65537
s = egcd(e1,e2)
s1 = s[1]
s2 = s[2]
s2 = - s2
m = pow(c1, s1, n) * pow(c2, s2, n) % n
print n2s(m)
7.cube root
if e=3,and n is very big,try it.
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from libnum import s2n,n2s
from gmpy2 import iroot
n = 0xB0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C478BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
e = 3
c = 545666236924510340010249577709750283325731706774285241719627277546281629429734726717293022303311450772262647904537263500252284243393598944613964442974546950954108203106726282255676706429218187217515454665602130999856741523362906632677988245886500953095201122016935004088287862399317170828388632964668574391252399791901016522260191839164586088073933168096433230663402492577707149742261018318811473591856287943664733276898405984282679026758294364432874973387827086342720762945025346962005339728347282927842299962927871005260338747371451546554777112213044710533502191671159066680035742327279159127279685106716107705888068319962657817786581813767331740609788885735155741039564703781141646102609725965697004923161084032164730408824475517786576979990372940555488021025837456038491436690372760376483602299268887032528766383572923258228355911069631275397149328319966792315903921085816103476508992023873616148326626245855060470294978538631677232260545724075728912626994884533001056079733734460116442499311813113038763837974777469202302071221647473459505245546281400799833123812072606012604323510933244028733287443734697557314202167934768160824072400916728008549350662843995750077421616789178835625661267955774815287104291379928002318796086248
i = 1
while 1:
res = iroot(c+i*n,3)
if(res[1] == True):
print res
break
if i%10000==0:
print "i="+str(i)
i = i+1
m = res[0]
print(n2s(m))
