0x00.RSA算法简介
选择两个大素数p和q，计算出模数N = p * q
计算φ = (p−1) * (q−1) 即N的欧拉函数，然后选择一个e (1<e<φ)，且e和φ互质
取e的模反数为d，计算方法: e * d ≡ 1 (mod φ)
对明文m进行加密：c = pow(m, e, N)，得到的c即为密文
对密文c进行解密，m = pow(c, d, N)，得到的m即为明文
相关资料：
http://www.freebuf.com/articles/others-articles/161475.html
https://www.anquanke.com/post/id/84632
有的题目文件保存在我的github : https://github.com/saltyfishyu/ctf-rsa-notes
0x01.
题目:直接给出p,q,e.
解法:求d.
0x02.
题目: n,d,e,c
解法：求明文
#!usr/bin/env python
# coding = utf-8
import libnum
n =
e =
d =
C =
M = pow(C,d,n)
print M
print libnum.n2s(M)
0x03.
题目:给c,n,e,求明文.
解法:由n得p,q.
#!usr/bin/env python
# coding = utf-8
def fastExpMod(b, e, m):
result = 1
while e != 0:
if (e&1) == 1:
result = (result * b) % m
e >>= 1
b = (b*b) % m
return result
def computeD(fn, e):
(x, y, r) = extendedGCD(fn, e)
if y < 0:
return fn + y
return y
def extendedGCD(a, b):
if b == 0:
return (1, 0, a)
x1 = 1
y1 = 0
x2 = 0
y2 = 1
while b != 0:
q = a / b
r = a % b
a = b
b = r
x = x1 - q*x2
x1 = x2
x2 = x
y = y1 - q*y2
y1 = y2
y2 = y
return(x1, y1, a)
def decryption(C, d, n):
return fastExpMod(C, d, n)
p =
q =
n = p * q
fn = (p - 1) * (q - 1)
e =
d = computeD(fn, e)
C =
M = decryption(C, d, n)
flag = str(hex(M))[2:-1]
print d
print flag.decode('hex')
通过以上脚本即可得出d,以及明文.
0x04.
题目:给公钥，密文，求明文.
解法:openssl+yafu+python脚本.
通过公钥查看模数n,e.
openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem通过yafu求p,q.
#!usr/bin/env python
# coding = utf-8
import math
import sys
from Crypto.PublicKey import RSA
keypair = RSA.generate(1024)
keypair.p =
keypair.q =
keypair.e =
keypair.n = keypair.p * keypair.q
Qn = long((keypair.p-1) * (keypair.q-1))
i = 1
while (True):
x = (Qn * i ) + 1
if (x % keypair.e == 0):
keypair.d = x / keypair.e
break
i += 1
private = open('private.pem','w')
private.write(keypair.exportKey())
private.close()通过以上脚本逆向编写密钥.
openssl rsautl -decrypt -in flag.enc -inkey private.pem -out flag.dec
cat flag.dec得到flag.
0x05.
题目：给公钥，密文（e=2)
解法:
通过公钥查看n,e.（此时可知e=2）
openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
这里上网查了一下当e=2时永远不应该被使用.
然后再查，这里引用D001UM3师傅的文章.
当e=2时，使用到了rabin算法。
在这里我站在D001UM3师傅的肩膀上，直接使用文章中的方法下载软件后.
python solve.py --verbose -k pubkey.pem --decrypt flag.enc得到flag.
python脚本之后有空再补充(咕咕咕).
0x06.
题目:使用相同的模数n，不同的私钥，加密同一明文消息.
解法:
判断为共模攻击.
网上找脚本，修改参数代入即可.
共模攻击相关及可参考脚本模板：
当目标数据为十六进制时
#!usr/bin/env python
#-*- coding=utf-8 -*-
import gmpy2
from libnum import *
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():
f1=open('','rb')
f2=open('','rb')
#n = int(raw_input("input n:"))
n=
#c1 = int(raw_input("input c1:"))
dataf1=f1.read()
c1=s2n(dataf1)
f1.close()
print c1
#c2 = int(raw_input("input c2:"))
dataf2=f2.read()
c2=s2n(dataf2)
f2.close()
print c2
#e1 = int(raw_input("input e1:"))
e1=
#e2 = int(raw_input("input e2:"))
e2=
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = gmpy2.invert(c1, n)
elif s2<0:
s2 = - s2
c2 = gmpy2.invert(c2, n)
m = gmpy2.powmod(c1,s1,n)*gmpy2.powmod(c2,s2,n)%n
print m
print n2s(m)
if __name__ == '__main__':
main()
当目标数据为十进制时
#!usr/bin/env python
#-*- coding=utf-8 -*-
import gmpy2
from libnum import *
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():
#n = int(raw_input("input n:"))
n=
#c1 = int(raw_input("input c1:"))
c1=
#c2 = int(raw_input("input c2:"))
c2=
#e1 = int(raw_input("input e1:"))
e1=
#e2 = int(raw_input("input e2:"))
e2=
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
# 求模反元素
if s1<0:
s1 = - s1
c1 = gmpy2.invert(c1, n)
elif s2<0:
s2 = - s2
c2 = gmpy2.invert(c2, n)
m = gmpy2.powmod(c1,s1,n)*gmpy2.powmod(c2,s2,n)%n
print m
print n2s(m)
if __name__ == '__main__':
main()
0x07.
题目:给公钥，密文.(e=3)
解法：
通过公钥查看n,e.（此时可知e=3）
openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
判断为小公钥指数攻击.
0x04提到了D001UM3师傅的肩膀，这次再次利用.
python solve.py --verbose -k pubkey.pem --decrypt flag.enc
运行很久之后得到flag.
python脚本之后有空再补充(咕咕咕).
0x08.
题目:随机数生成p,q?(不太懂
题目来源ISITDTU CTF 2018 Quals Simple Rsa
from Crypto.Util.number import *
import random
flag = 'Hidden'
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 modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
#raise Exception('modular inverse does not exist')
print "aaa"
else:
return x % m
def next_prime(n):
num = n + 1
while True:
if isPrime(num):
return num
num += 1
p = random.randint(1<<251,1<<252)
i = 10
p = next_prime(p)
p1 = next_prime(p*10)
p2 = next_prime(p1*10)
p3 = next_prime(p2*10)
N = p*p1*p2*p3
e = 65537
c = pow(bytes_to_long(flag),e,N)
print c
#153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
print N
#603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
解法：
from functools import reduce
from math import sqrt
from Crypto.Util.number import *
def next_prime(n):
num = n + 1
while True:
if isPrime(num):
return num
num += 1
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 modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def bin_srch(target, lo, hi, f):
if lo >= hi:
return lo
mid = (lo+hi)//2
if f(mid) > target:
return bin_srch(target, lo, mid-1, f)
else:
return bin_srch(target, mid+1, hi, f)
def poly(p):
return 1000000 * pow(p, 4)
n = 603040899191765499692105412408128039799635285914243838639458755491385487537245112353139626673905393100145421529413079339538777058510964724244525164265239307111938912323072543529589488452173312928447289267651249034509309453696972053651162310797873759227949341560295688041964008368596191262760564685226946006231
c = 153348390614662968396805701018941225929976855876673665545678808357493865670852637784454103632206407687489178974011663144922612614936251484669376715328818177626125051048699207156003563901638883835345344061093282392322541967439067639713967480376436913225761668591305793224841429397848597912616509823391639856132
guess = bin_srch(n, 1<<251, 1<<252, poly)
p = 0
for g in range(-1000+guess, 1000+guess):
if n % g == 0:
p = g
break
primes = [p]
for i in range(3):
primes.append(next_prime(primes[i]*10))
print 'primes:', primes
phi = reduce(lambda a,b: a*(b-1), primes, 1)
print(long_to_bytes(pow(c, modinv(65537, phi), n)).decode('utf-8'))
题目来源2018柏鹭杯 crypt1
from Crypto.Util.number import *
import random
def next_prime(n):
num = n + 1
while True:
if isPrime(num):
return num
num += 1
p = random.randint(1<<3071,1<<3072)
p = next_prime(p)
q = next_prime(p*10)
N = p*q
e = 65537
c = pow(bytes_to_long(flag),e,N)
print N#247157208312655169175097941364280738161257111976460225724719907081110265510517450181419502794457206227461600647913804553439171851865273449559295717229024951735351965745325255241561391509015823198303928588939850683031392486366218841593013566932215141428061199015117025898704736991786081007198271335363347647516874679013119543722851148642512142186199102168074461255284546705588056994149297326331376082141145137980534967406372164077378650248545875219877244489040506317293082270408705203779841533080244655519849164084793887915122847280359452339072498784918027724621588636245527176960457003310429876627882173282069366037431766179722648353575718417895929519296072344510519198593252963273537190447967056699273665756186541135880261688073100218736960343554003491651502334045257343825793705434779809139021362473746587814528428007114308414633338220797896397738142172067161950968365434368211510967904096253326804711795198906393597153228365711080786247894858858419136771806150038968465644512536135428099037524022644906606239281576512245480765249280626544900781649017542649977530381598608436485399917576052247750573936190833224008929770080605906041913084656134359260509037195783858871830359437278131656343708211575987756873026171223324073191307367943843353573378426157170935012284820053625264544030714057464690450568057598110227083895395913850243271935830358181622027323185508807486853971929523201869477689585619024238113916052252320578711256593537267591407960305853736136636628575478996733430026632486500743561965770413140633948002705696925426367918545515713035754606128166993229587155817506068035187995926746472892280477401942441831391756895131543049750847590716935278314226902082626392655666615086297442052602217416486188297831289978272258543231414975069191549588547253936829655332588805672513945883351937495650167502066292697223592894483418517613405613285519159
print c#152721025887735064764471379084548069204525956728140596238274397757947415316727016281416993518884790524343567541799262176820909148208728616947040227306302164641933331109468512979068186962047716308015535717796123080303496277784765187481185086876434873226524784636408104495312136956587251145463229424950634548624036265557622592089071331292811066840281494102799063634204855779210798330603868025111521826209601342683209160845433746624786171189961029265101816540639855230011618388675527443511618729301028631422873421421991470450059414988968787693753741941765791793672069240992955177930884210118700416564364129283739917229225845073750451244070534919112957275948312337882004219145847493047815403283126471638320784008475284616178697542301935170768573588093196019976675846311280356987370969400610196847990069257614148181804915868273001764028563852238142447411811579695265293746037324400494199877368049162903819737962946786971556872009326814914717430484711885484790156341127433550909206551293806568904858726942820132521566970376839336895645431303013575622422180179687172859250687080526393904583834607514619581478966664406178290247731116920836372943133394640322159512633671870473674514938423231596849301615200001553851411828993918474534316510609878376462094608058640335426907349648369552864820322464995077358198844334320833893207364879282292959161203675080110629771237503657412087961891443054530286088807186134851425688726147108076040204500951624929585070273336203814962656253259257806100191430918121713005141607192112560560371475173081441671613602480052062955279287813475764285469835557663176529059039540417149792518941598550609678298901186032272305421028365295602810159191055078633881059737011784127699357480578433240110432805495328517379885306237631225477566136721077348329866885731002878563684349453668924250445128775992616650275173644658245397235667490402628
解法：
n=247157208312655169175097941364280738161257111976460225724719907081110265510517450181419502794457206227461600647913804553439171851865273449559295717229024951735351965745325255241561391509015823198303928588939850683031392486366218841593013566932215141428061199015117025898704736991786081007198271335363347647516874679013119543722851148642512142186199102168074461255284546705588056994149297326331376082141145137980534967406372164077378650248545875219877244489040506317293082270408705203779841533080244655519849164084793887915122847280359452339072498784918027724621588636245527176960457003310429876627882173282069366037431766179722648353575718417895929519296072344510519198593252963273537190447967056699273665756186541135880261688073100218736960343554003491651502334045257343825793705434779809139021362473746587814528428007114308414633338220797896397738142172067161950968365434368211510967904096253326804711795198906393597153228365711080786247894858858419136771806150038968465644512536135428099037524022644906606239281576512245480765249280626544900781649017542649977530381598608436485399917576052247750573936190833224008929770080605906041913084656134359260509037195783858871830359437278131656343708211575987756873026171223324073191307367943843353573378426157170935012284820053625264544030714057464690450568057598110227083895395913850243271935830358181622027323185508807486853971929523201869477689585619024238113916052252320578711256593537267591407960305853736136636628575478996733430026632486500743561965770413140633948002705696925426367918545515713035754606128166993229587155817506068035187995926746472892280477401942441831391756895131543049750847590716935278314226902082626392655666615086297442052602217416486188297831289978272258543231414975069191549588547253936829655332588805672513945883351937495650167502066292697223592894483418517613405613285519159
c=152721025887735064764471379084548069204525956728140596238274397757947415316727016281416993518884790524343567541799262176820909148208728616947040227306302164641933331109468512979068186962047716308015535717796123080303496277784765187481185086876434873226524784636408104495312136956587251145463229424950634548624036265557622592089071331292811066840281494102799063634204855779210798330603868025111521826209601342683209160845433746624786171189961029265101816540639855230011618388675527443511618729301028631422873421421991470450059414988968787693753741941765791793672069240992955177930884210118700416564364129283739917229225845073750451244070534919112957275948312337882004219145847493047815403283126471638320784008475284616178697542301935170768573588093196019976675846311280356987370969400610196847990069257614148181804915868273001764028563852238142447411811579695265293746037324400494199877368049162903819737962946786971556872009326814914717430484711885484790156341127433550909206551293806568904858726942820132521566970376839336895645431303013575622422180179687172859250687080526393904583834607514619581478966664406178290247731116920836372943133394640322159512633671870473674514938423231596849301615200001553851411828993918474534316510609878376462094608058640335426907349648369552864820322464995077358198844334320833893207364879282292959161203675080110629771237503657412087961891443054530286088807186134851425688726147108076040204500951624929585070273336203814962656253259257806100191430918121713005141607192112560560371475173081441671613602480052062955279287813475764285469835557663176529059039540417149792518941598550609678298901186032272305421028365295602810159191055078633881059737011784127699357480578433240110432805495328517379885306237631225477566136721077348329866885731002878563684349453668924250445128775992616650275173644658245397235667490402628
import gmpy2
from Crypto.Util.number import *
k=gmpy2.iroot(n//10+1,2)[0]+1
print(k)
for i in range(0xfffffff):
f=k-i
if i%10000==0:
print i
if n%f==0:
print (i,n)
break
p=f
q=n//f
assert(p*q==n)
phi=(p-1)*(q-1)
e= 65537
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
0x09.
题目: gmpy.next_prime() Examples / small Modular 如何通过导出公钥来求解rsa
题目来源2018百越杯初赛常规RSA
#!/usr/bin/env python3
import gmpy2
from Crypto.Util.number import getPrime
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from base64 import b64encode
flag = open('flag', 'r').read().strip() * 23
def encrypt(p, q, e, msg):
while True:
n = p * q
try:
phi = (p - 1)*(q - 1)
pubkey = RSA.construct((int(n), int(e)))
key = PKCS1_v1_5.new(pubkey)
enc = b64encode(key.encrypt(msg))
return enc
except:
p = gmpy2.next_prime(p**2 + q**2)
q = gmpy2.next_prime(2*p*q)
e = gmpy2.next_prime(e**2)
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((n, e))
with open('pubkey.pem', 'wb') as f:
f.write(pubkey.exportKey())
with open('flag.enc', 'wb') as g:
g.write(encrypt(p, q, e, flag.encode()))
exp.py :
import gmpy2
import base64
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
def decrypt_RSA(cipherfile):
n = 62078208638445817213739226854534031566665495569130972218813975279479576033261
e = 9850747023606211927
p = 336771668019607304680919844592337860739
q = 184333227921154992916659782580114145999
cipher = open(cipherfile, "r").read()
while True:
try:
# key = open(privkey, "r").read()
phi = (p - 1)*(q - 1)
d = gmpy2.invert(e, phi)
# pubkey = RSA.construct((long(n), long(e)))
privkey = RSA.construct((long(n), long(e), long(d)))
key = PKCS1_v1_5.new(privkey)
decrypted = key.decrypt(base64.b64decode(cipher), None)
print decrypted
break
except Exception as ex:
print ex
p = gmpy2.next_prime(p**2 + q**2)
q = gmpy2.next_prime(2*p*q)
e = gmpy2.next_prime(e**2)
n = long(p)*long(q)
decrypt_RSA("flag.enc")
题目来源[ASIS FINAL 2016] - RSA
#!/usr/bin/python
import gmpy
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
flag = open('flag', 'r').read() * 30
def ext_rsa_encrypt(p, q, e, msg):
m = bytes_to_long(msg)
while True:
n = p * q
try:
phi = (p - 1)*(q - 1)
d = gmpy.invert(e, phi)
pubkey = RSA.construct((long(n), long(e)))
key = PKCS1_v1_5.new(pubkey)
enc = key.encrypt(msg).encode('base64')
return enc
except:
p = gmpy.next_prime(p**2 + q**2)
q = gmpy.next_prime(2*p*q)
e = gmpy.next_prime(e**2)
p = getPrime(128)
q = getPrime(128)
n = p*q
e = getPrime(64)
pubkey = RSA.construct((long(n), long(e)))
f = open('pubkey.pem', 'w')
f.write(pubkey.exportKey())
g = open('flag.enc', 'w')
g.write(ext_rsa_encrypt(p, q, e, flag))
exp.py :
import gmpy
import base64
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
def decrypt_RSA(cipherfile):
n = 98099407767975360290660227117126057014537157468191654426411230468489043009977
e = 12405943493775545863
p = 311155972145869391293781528370734636009
q = 315274063651866931016337573625089033553
cipher = open(cipherfile, "r").read()
while True:
try:
# key = open(privkey, "r").read()
phi = (p - 1)*(q - 1)
d = gmpy.invert(e, phi)
# pubkey = RSA.construct((long(n), long(e)))
privkey = RSA.construct((long(n), long(e), long(d)))
key = PKCS1_v1_5.new(privkey)
decrypted = key.decrypt(base64.b64decode(cipher), None)
print decrypted
break
except Exception as ex:
print ex
p = gmpy.next_prime(p**2 + q**2)
q = gmpy.next_prime(2*p*q)
e = gmpy.next_prime(e**2)
n = long(p)*long(q)
decrypt_RSA("flag.enc")
题目来源ASIS CTF Finals 2017: Handicraft RSA
#!/usr/bin/python
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from secret import s, FLAG
def gen_prime(s):
while True:
r = getPrime(s)
R = [r]
t = int(5 * s / 2) + 1
for i in range(0, t):
R.append(r + getRandomRange(0, 4 * s ** 2))
p = reduce(lambda a, b: a * b, R, 2) + 1
if isPrime(p):
if len(bin(p)[2:]) == 1024:
return p
while True:
p = gen_prime(s)
q = gen_prime(s)
n = p * q
e = 65537
d = inverse(e, (p-1)*(q-1))
if len(bin(n)[2:]) == 2048:
break
msg = FLAG
key = RSA.construct((long(n), long(e), long(d), long(p), long(p)))
for _ in xrange(s):
enc = key.encrypt(msg, 0)[0]
msg = enc
print key.publickey().exportKey()
print '-' * 76
print enc.encode('base64')
print '-' * 76
exp.py :
import base64
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
def gcd(a,b):
while b != 0:
t = b
b = a % b
a = t
return a
# Pollard's p-1 algorithm
# https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
# this is really slow on stock python2, use either python3 or some JITer
def factor(n):
a = 2
b = 2
while True:
if b % 10000 == 0:
print(b)
a = pow(a, b, n)
p = gcd(a - 1, n)
if 1 < p < n:
print("FOUND " + str(p))
return p
b += 1
def decrypt(n, p, q):
assert p * q == n
e = 65537
d = inverse(e, (p-1)*(q-1))
key = RSA.construct((long(n), long(e), long(d), long(p), long(q)))
msg = base64.b64decode("eER0JNIcZYx/t+7lnRvv8s8zyMw8dYspZlne0MQUatQNcnDL/wnHtkAoNdCalQkpcbnZeAz4qeMX5GBmsO+BXyAKDueMA4uy3fw2k/dqFSsZFiB7I9M0oEkqUja52IMpkGDJ2eXGj9WHe4mqkniIayS42o4p9b0Qlz754qqRgkuaKzPWkZPKynULAtFXF39zm6dPI/jUA2BEo5WBoPzsCzwRmdr6QmJXTsau5BAQC5qdIkmCNq7+NLY1fjOmSEF/W+mdQvcwYPbe2zezroCiLiPNZnoABfmPbWAcASVU6M0YxvnXsh2YjkyLFf4cJSgroM3Aw4fVz3PPSsAQyCFKBA==")
for _ in xrange(20):
enc = key.decrypt(msg)
msg = enc
print repr(msg)
asciikey = """-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEAq+m7iHurBa9G8ujEiTpZ
71aHOVNhQXpd6jCQNhwMN3hD6JHkv0HSxmJwfGe0EnXDtjRraWmS6OYzT4+LSrXs
z9IkWGzRlJ4lC7WHS8D3NWIWYHCP4TRt2N0TlWXWm9nFCrEXqQ3IWgYQpQvKzsds
etnIZJL1tf1wQzGE6rbkbvURlUBbzBSuidkmi0kY5Qxp2Jfb6OUI647zx2dPxJpD
ffSCNffVIDUYOvrgYxIhs5HmCF3XECC3VfaKtRceL5JM8R0qz5nVU2Ns8hPvSVP+
7/i7G447cjW151si0joB7RpBplu44Vk8TXXDAk0JZdW6KwJn7ITaX04AAAAAAAAA
AQIDAQAB
-----END PUBLIC KEY-----"""
key = RSA.importKey(asciikey)
n = int(key.n)
# p = 139457081371053313087662621808811891689477698775602541222732432884929677435971504758581219546068100871560676389156360422970589688848020499752936702307974617390996217688749392344211044595211963580524376876607487048719085184308509979502505202804812382023512342185380439620200563119485952705668730322944000000001
p = factor(key.n)
q = n / p
decrypt(n, p, q)
一直没有深入学习过密码学,也只能多收集点wp希望比赛能做出题,我好菜啊.
还不快抢沙发