灵感来自于某一年提出的单兵计划（其实是自己懒拖到现在才开始）密码学自己真的从来没有接触过。从0开始的，👴们勿喷呜呜呜
babyrsa | 已知 公钥（n, e） 和 密文 c 求 明文 m
from Crypto.Util.number import *
from flag import flag
def gen_prime(n):
res = 1
for i in range(15):
res *= getPrime(n)
return res
if __name__ == '__main__':
n = gen_prime(32)
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(n)
print(c)
# 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
# 14322038433761655404678393568158537849783589481463521075694802654611048898878605144663750410655734675423328256213114422929994037240752995363595
先用yafu分离n为 q 和 p，将n另存为data.txt的时候记得最后要换行。
\yafu-x64.exe "factor(@)" -batchfile data.txt
然后写脚本还原即可：
import libnum
from Crypto.Util.number import long_to_bytes
c = 14322038433761655404678393568158537849783589481463521075694802654611048898878605144663750410655734675423328256213114422929994037240752995363595
n = 17290066070594979571009663381214201320459569851358502368651245514213538229969915658064992558167323586895088933922835353804055772638980251328261
#n = int("",16)
e = 65537
#e = int("",16)
P1 = 4278428893
P2 = 3207148519
P3 = 2804303069
P4 = 2923072267
P5 = 2706073949
P6 = 3939901243
P7 = 2970591037
P8 = 2463878387
P9 = 2370292207
P10 = 2338725373
P11 = 3654864131
P12 = 2217990919
P13 = 3831680819
P14 = 2794985117
P15 = 4093178561
d = libnum.invmod(e, (P1 - 1) * (P2 - 1) * (P3 - 1) * (P4 - 1) * (P5 - 1) * (P6 - 1) * (P7 - 1) * (P8 - 1) * (P9 - 1) * (P10 - 1) * (P11 - 1) * (P12 - 1) * (P13 - 1) * (P14 - 1) * (P15 - 1))
m = pow(c, d, n) # m 的十进制形式
string = long_to_bytes(m) # m明文
print(string) # 结果为 b‘ m ’ 的形式
Small d | 维纳攻击
from secret import flag
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
d = getPrime(32)
e = inverse(d, (p-1)*(q-1))
n = p*q
m = bytes_to_long(flag)
c = pow(m,e,n)
print(c)
print(e)
print(n)
# c = 6755916696778185952300108824880341673727005249517850628424982499865744864158808968764135637141068930913626093598728925195859592078242679206690525678584698906782028671968557701271591419982370839581872779561897896707128815668722609285484978303216863236997021197576337940204757331749701872808443246927772977500576853559531421931943600185923610329322219591977644573509755483679059951426686170296018798771243136530651597181988040668586240449099412301454312937065604961224359235038190145852108473520413909014198600434679037524165523422401364208450631557380207996597981309168360160658308982745545442756884931141501387954248
# e = 8614531087131806536072176126608505396485998912193090420094510792595101158240453985055053653848556325011409922394711124558383619830290017950912353027270400567568622816245822324422993074690183971093882640779808546479195604743230137113293752897968332220989640710311998150108315298333817030634179487075421403617790823560886688860928133117536724977888683732478708628314857313700596522339509581915323452695136877802816003353853220986492007970183551041303875958750496892867954477510966708935358534322867404860267180294538231734184176727805289746004999969923736528783436876728104351783351879340959568183101515294393048651825
# n = 19873634983456087520110552277450497529248494581902299327237268030756398057752510103012336452522030173329321726779935832106030157682672262548076895370443461558851584951681093787821035488952691034250115440441807557595256984719995983158595843451037546929918777883675020571945533922321514120075488490479009468943286990002735169371404973284096869826357659027627815888558391520276866122370551115223282637855894202170474955274129276356625364663165723431215981184996513023372433862053624792195361271141451880123090158644095287045862204954829998614717677163841391272754122687961264723993880239407106030370047794145123292991433
脚本：
import gmpy2
import libnum
def continuedFra(x, y):
"""计算连分数
:param x: 分子
:param y: 分母
:return: 连分数列表
"""
cf = []
while y:
cf.append(x // y)
x, y = y, x % y
return cf
def gradualFra(cf):
"""计算传入列表最后的渐进分数
:param cf: 连分数列表
:return: 该列表最后的渐近分数
"""
numerator = 0
denominator = 1
for x in cf[::-1]:
# 这里的渐进分数分子分母要分开
numerator, denominator = denominator, x * denominator + numerator
return numerator, denominator
def solve_pq(a, b, c):
"""使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
:param a:x^2的系数
:param b:x的系数
:param c:pq
:return:p，q
"""
par = gmpy2.isqrt(b * b - 4 * a * c)
return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
"""计算列表所有的渐近分数
:param cf: 连分数列表
:return: 该列表所有的渐近分数
"""
gf = []
for i in range(1, len(cf) + 1):
gf.append(gradualFra(cf[:i]))
return gf
def wienerAttack(e, n):
"""
:param e:
:param n:
:return: 私钥d
"""
cf = continuedFra(e, n)
gf = getGradualFra(cf)
for d, k in gf:
if k == 0: continue
if (e * d - 1) % k != 0:
continue
phi = (e * d - 1) // k
p, q = solve_pq(1, n - phi + 1, n)
if p * q == n:
return d
n= 19873634983456087520110552277450497529248494581902299327237268030756398057752510103012336452522030173329321726779935832106030157682672262548076895370443461558851584951681093787821035488952691034250115440441807557595256984719995983158595843451037546929918777883675020571945533922321514120075488490479009468943286990002735169371404973284096869826357659027627815888558391520276866122370551115223282637855894202170474955274129276356625364663165723431215981184996513023372433862053624792195361271141451880123090158644095287045862204954829998614717677163841391272754122687961264723993880239407106030370047794145123292991433
e= 8614531087131806536072176126608505396485998912193090420094510792595101158240453985055053653848556325011409922394711124558383619830290017950912353027270400567568622816245822324422993074690183971093882640779808546479195604743230137113293752897968332220989640710311998150108315298333817030634179487075421403617790823560886688860928133117536724977888683732478708628314857313700596522339509581915323452695136877802816003353853220986492007970183551041303875958750496892867954477510966708935358534322867404860267180294538231734184176727805289746004999969923736528783436876728104351783351879340959568183101515294393048651825
c= 6755916696778185952300108824880341673727005249517850628424982499865744864158808968764135637141068930913626093598728925195859592078242679206690525678584698906782028671968557701271591419982370839581872779561897896707128815668722609285484978303216863236997021197576337940204757331749701872808443246927772977500576853559531421931943600185923610329322219591977644573509755483679059951426686170296018798771243136530651597181988040668586240449099412301454312937065604961224359235038190145852108473520413909014198600434679037524165523422401364208450631557380207996597981309168360160658308982745545442756884931141501387954248
d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())
babyxor | 异或
from secret import *
ciphertext = []
for f in flag:
ciphertext.append(f ^ key)
print(bytes(ciphertext).hex())
# e9e3eee8f4f7bffdd0bebad0fcf6e2e2bcfbfdf6d0eee1ebd0eabbf5f6aeaeaeaeaeaef2
被异或后，然后再异或一次就是原文。
注意一个地方，异或要以str或者int形式进行异或，byte不行
key = 0x8f
ciphertext_hex = "e9e3eee8f4f7bffdd0bebad0fcf6e2e2bcfbfdf6d0eee1ebd0eabbf5f6aeaeaeaeaeaef2"
ciphertext_bytes = bytes.fromhex(ciphertext_hex)
plaintext = []
for byte in ciphertext_bytes:
decrypted_byte = byte ^ key
plaintext.append(decrypted_byte)
flag = ''.join([chr(byte) for byte in plaintext])
print(flag)
Affine | 仿射密码
from flag import flag, key
modulus = 256
ciphertext = []
for f in flag:
ciphertext.append((key[0]*f + key[1]) % modulus)
print(bytes(ciphertext).hex())
# dd4388ee428bdddd5865cc66aa5887ffcca966109c66edcca920667a88312064
from Crypto.Util.number import *
from gmpy2 import *
ciphertext_hex = "dd4388ee428bdddd5865cc66aa5887ffcca966109c66edcca920667a88312064"
ciphertext_bytes = bytes.fromhex(ciphertext_hex)
print(ciphertext_bytes)
ciphertext_bytes = "\xddC\x88\xeeB\x8b\xdd\xddXe\xccf\xaaX\x87\xff\xcc\xa9f\x10\x9cf\xed\xcc\xa9 fz\x881 d"
# for f in flag:
# ciphertext.append((key[0]*f + key[1]) % modulus) 和mod一样
for a in range(256):
for b in range(256):
flag = ''
a = inverse(a,256) #inverse求逆元
for i in ciphertext_bytes :
flag += chr((ord(i)-b)*a %256)
if 'flag' in flag:
print(flag)
# from Crypto.Util.number import *
# from gmpy2 import *
# c=0xdd4388ee428bdddd5865cc66aa5887ffcca966109c66edcca920667a88312064
# c='\xddC\x88\xeeB\x8b\xdd\xddXe\xccf\xaaX\x87\xff\xcc\xa9f\x10\x9cf\xed\xcc\xa9 fz\x881 d'
# for a in range(256):
# for b in range(256):
# flag=''
# a_=inverse(a,256)
# for i in c:
# flag+=chr((ord(i)-b)*a_ %256)
# if 'flag' in flag:
# print(flag)
babyaes | aes_cbc模式
from Crypto.Cipher import AES
import os
from flag import flag
from Crypto.Util.number import *
def pad(data):
return data + b"".join([b'\x00' for _ in range(0, 16 - len(data))])
def main():
flag_ = pad(flag)
key = os.urandom(16) * 2
iv = os.urandom(16)
print(bytes_to_long(key) ^ bytes_to_long(iv) ^ 1)
aes = AES.new(key, AES.MODE_CBC, iv)
enc_flag = aes.encrypt(flag_)
print(enc_flag)
if __name__ == "__main__":
main()
# 3657491768215750635844958060963805125333761387746954618540958489914964573229
# b'>]\xc1\xe5\x82/\x02\x7ft\xf1B\x8d\n\xc1\x95i'
使用了一个密钥 Key 和初始化向量 IV,选择的CBC模式加密
urandom：
语法 os.urandom（size）
参数：
size:字符串随机字节的大小
返回值：该方法返回一个字符串，该字符串表示适合加密使用的随机字节。
例 os.urandom(1)
输出：b'\x91'
二进制：10010001 （8bits）
os.urandom()与十六进制\xhh
os.urandom()函数在python官方文档中做出了这样的解释:
Return a string of n random bytes suitable for cryptographic use.
即返回一个长为n个bytes的string，然后很适合用于加密。python的这个函数实际上是在读取OS操作系统提供的随机源，关于加密应用暂且不考虑。
测试一下：
for i in range(10):
print(os.urandom(i))
output:
b''
b'6'
b'Rj'
b'}\x13\xca'
b't\xc79w'
b'UF^f\x8b'
b'D\xf6\x14b\xd9n'
b'\xe4\xa5\xc1\t\x0b\xf4u'
b'\x8d\x94A\xd4qO\x07\x9d'
b'\x86Q\xe2\n\xfa\xaa\xf0\xd5H'
为了方便确认这个是个字符串的长度，调整代码：
for i in range(10):
print(len(os.urandom(i)))
# 0
# 1
# 2
# 3
# 4
# 5
# 6
# 7
# 8
# 9
即，在较长字符串中\x的作用域只有后面紧跟的两字符，而我们知道十六进制表示成二进制0000~1111占4bits,其中0000为十进制0、1111为十进制15。所以两个十六进制位数正好是8bits，即一个byte，是这样再看urandom的输出：
b''---0 byte
b'6'---1 byte
b'Rj'---2 bytes
b'}\x13\xca'---1+1+1---3 bytes
b't\xc79w'---1+1+2---4 bytes
b'UF^f\x8b'---4+1---5 bytes
b'D\xf6\x14b\xd9n'----1+1+1+1+1+1---6 bytes
key=os.urandom(16)*2
iv=os.urandom(16)
可知：key是32bytes，256bits ；iv是16bytes ，128bits
key^iv ，那么只有 iv 与 key的低128位相异或，所以key的高128位是固定不变的。所以输出结果的高128bits，就是key的高128bits，进而可以得到key的所有值256bits。
之后key的低128bits，与输出结果的低128bits和1 相异或，所得结果就是 iv的值了
key，iv得到后直接aes.decrypt()解密就ok了
#python3
from Crypto.Cipher import AES
import os
from gmpy2 import*
from Crypto.Util.number import*
xor = 3657491768215750635844958060963805125333761387746954618540958489914964573229
enc_flag = b'>]\xc1\xe5\x82/\x02\x7ft\xf1B\x8d\n\xc1\x95i'
out=long_to_bytes(xor)
# print(out)
key = out[:16]*2
# print(key)
iv = bytes_to_long(key[16:]) ^ bytes_to_long(out[16:]) ^ 1
iv = long_to_bytes(iv)
print(iv)
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc_flag)
print(flag)
# #python3
# from Crypto.Cipher import AES
# import os
# from gmpy2 import*
# from Crypto.Util.number import*
# xor = 91144196586662942563895769614300232343026691029427747065707381728622849079757
# enc_flag = b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
# out = long_to_bytes(xor)
# key = out[:16]*2
# # print(key)
# iv = bytes_to_long(key[16:])^bytes_to_long(out[16:])
# # print(iv)
# iv = long_to_bytes(iv)
# # print(iv)
# aes = AES.new(key,AES.MODE_CBC,iv)
# flag = aes.decrypt(enc_flag)
# print(flag)
入门题型整理
rsa加密的过程：
- 随便找出两个 整数 q 和 p （q，p互素，即：公因数只有1）
- *求出n = q p **
-
φ(n) = （p-1）*（q-1）欧拉公式
- 公钥 e ：随机取，要求 ：
e 和 φ(n)互素（公因数只有 1；**1< e < φ(n)**）；
- 私钥 d ：
ed ≡ 1 (mod φ(n)) （ed 除以 φ(n) 的 余数 为 1 ）
已知 p ，q，e求 d |（ed 除以 (q-1)(p-1) 的 余数 为 1 ）
import gmpy2
p = 38456719616722997
q = 44106885765559411
e = 65537
s = (p-1)*(q-1)
d = gmpy2.invert(e,s)
print ("dec: " + str(d))
print ("hex: " + hex(d))
已知 公钥（n, e） 和 密文 c 求 明文 m
见上面题解babyrsa
已知密文文件 flag.enc/cipher.bin/flag.b64 和 公钥文件 pubkey.pem /key.pem /key.pub求解明文 m
方法一：(key.pem 和 cipher.bin)
直接用 RsaCtfTool进行破解：
python3 RsaCtfTool.py --publickey key.pem --uncipherfile cipher.bin
方法二：（flag.b64 和 key.pub）
先处理flag.b64（将flag.b64中的内容进行解 base64操作）
使用 notepad++ 打开 flag.b64文件使用 插件中的 MIME Tools 中的 base64 decode 将文件内容解密，然后另保存为 flag.enc 文件
然后使用 RsaCtfTool 工具进行破解：
python3 RsaCtfTool.py --publickey /root/desktop/share/key.pem --uncipherfile /root/desktop/share/flag.enc
方法三：提取 pubkey.pem 中的 参数
openssl rsa -pubin -text -modulus -in warmup -in pubkey.pem
其次，用 yafu 分解 n 得到 q，p
然后 制作 私钥 ：生成私钥文件 private.pem
python rsatool.py -o private.pem -e 65537 -p 275127860351348928173285174381581152299 -q 319576316814478949870590164193048041239
最后 用private.pem文件 解密 flag.enc文件
openssl rsautl -decrypt -in flag.enc -inkey private.pem
已知私钥 private.pem 和密文 flag.enc
方法一：利用 rsactftool。
python RsaCtfTool.py --private private.pem --uncipherfile flag.enc
方法二：利用 openssl：
openssl rsautl -decrypt -in flag.enc -inkey private.pem
已知c ，e，n（非常大），和 dp，dq，求解明文m
领航杯2019的一道题，EasyRSA：给了e, n, c,由于特别大，没法直接用质因数分解求得 q， p
还给了
qhint = q % （p - 1） # 其实 qhint = dq
phint = d % （p - 1） # 其实 phint = dp
import gmpy2
import libnum
e=65537
n=16969752165509132627630266968748854330340701692125427619559836488350298234735571480353078614975580378467355952333755313935516513773552163392952656321490268452556604858966899956242107008410558657924344295651939297328007932245741660910510032969527598266270511004857674534802203387399678231880894252328431133224653544948661283777645985028207609526654816645155558915197745062569124587412378716049814040670665079480055644873470756602993387261939566958806296599782943460141582045150971031211218617091283284118573714029266331227327398724265170352646794068702789645980810005549376399535110820052472419846801809110186557162127
dp=1781625775291028870269685257521108090329543012728705467782546913951537642623621769246441122189948671374990946405164459867410646825591310622618379116284293794090970292165263334749393009999335413089903796624326168039618287078192646490488534062803960418790874890435529393047389228718835244370645215187358081805
c=0x6c78dcee37830f3ec4ab4989d40fbb595060b3fbc395d52ad26defc13372c1a3948c5388f4e450e46e016c7803133d6881e5efc3b90a4789448097c94124590b1e7949f2524d7edccd61a27691c18d090ac1f54643b563141306045417581e3b263f4ad2816136a48b106f3058b08e2a810f4ae8ef25916cc110b41ac8158ce69ecbe20fc60c1ddb20154c6646bc5142aefe47abf053a8ac949d5bc057bb18b191ad08070fe9ec5d76b1fceae685514532448c1b388b2d38e7241ac19c296e95e4e021a3a4015d909a1d53a2eb7fa86f6329f4e6c937f958be576c58fab4d9c9126999c99bb28718efc41a6f5db52b47942a2ddf21639f020b5489699cf22b46
for i in range(1,65538):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)//i)+1)==0:
p=((dp*e-1)//i)+1
q=n//(((dp*e-1)//i)+1)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)%phi
print(libnum.n2s(pow(c,d,n)))
已知n（非常大），e，d求p，q（无法直接 从n分解）
# python2
from gmpy2 import invert
from md5 import md5
from secret import p,q
e = 65537
n = p*q
phi = (p-1)*(q-1)
d = invert(e,phi)
print n,e,d
print "flag{%s}" % md5(str(p+q)).hexdigest()
#python 2
import random
from md5 import md5
def gcd(a, b):
if a < b:
a, b = b, a
while b != 0:
temp = a % b
a = b
b = temp
return a
def getpq(n,e,d):
p = 1
q = 1
while p==1 and q==1:
k = d * e - 1
g = random.randint ( 0 , n )
while p==1 and q==1 and k % 2 == 0:
k /= 2
y = pow(g,k,n)
if y!=1 and gcd(y-1,n)>1:
p = gcd(y-1,n)
q = n/p
return p,q
def main():
n = 16352578963372306131642407541567045533766691177138375676491913897592458965544068296813122740126583082006556217616296009516413202833698268845634497478988128850373221853516973259086845725813424850548682503827191121548693288763243619033224322698075987667531863213468223654181658012754897588147027437229269098246969811226129883327598021859724836993626315476699384610680857047403431430525708390695622848315322636785398223207468754197643541958599210127261345770914514670199047435085714403641469016212958361993969304545214061560160267760786482163373784437641808292654489343487613446165542988382687729593384887516272690654309
e = 65537
d = 9459928379973667430138068528059438139092368625339079253289560577985304435062213121398231875832264894458314629575455553485752685643743266654630829957442008775259776311585654014858165341757547284112061885158006881475740553532826576260839430343960738520822367975528644329172668877696208741007648370045520535298040161675407779239300466681615493892692265542290255408673533853011662134953869432632554008235340864803377610352438146264524770710345273439724107080190182918285547426166561803716644089414078389475072103315432638197578186106576626728869020366214077455194554930725576023274922741115941214789600089166754476449453
p,q = getpq(n,e,d)
print p
print q
print "Flag: flag{%s}" %md5(str(p + q)).hexdigest()
if __name__ == '__main__':
main()
提取私钥中的信息
python RsaCtfTool.py --key private.pem --dumpkey
用公钥pub.key/pub.pem文件生成 私钥文件
python RsaCtfTool.py --publickey pubkey.pem --private > private.pem
或
python RsaCtfTool.py --publickey pub.key --private > private.key
n分解出多个不同的因子时 ，求明文m
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
m=???
对n进行质因数分解，得到了3个质因数，（这里知道欧拉公式的性质的话 就很好解)
φ(x * y * z) = φ(x) * φ(y) * φ(z)=(x-1)(y-1)(z-1)
# python2
import gmpy2
from Crypto.Util.number import long_to_bytes
n= 544187306850902797629107353619267427694837163600853983242783
e= 39293
c= 439254895818320413408827022398053685867343267971712332011972
p1 = 67724172605733871
p2 = 11571390939636959887
p3 = 694415063702720454699679
phi = (p1-1)*(p2-1)*(p3-1)
d = gmpy2.invert(e, phi)
m = pow(c, d, n)
print long_to_bytes(m)
爆破攻击
低加密指数分解攻击（比如 e=2,e=3）
在 RSA 中 e 也称为加密指数。由于 e 是可以随意选取的，选取小一点的 e 可以缩短加密时间（比如 e=2,e=3），但是选取不当的话，就会造成安全问题。
下面就是e选取的太小导致存在的安全问题：
e=2把密文c开平方求解
RSA加密，由于e只有2，相当于把明文m平方而已，得到的c也比n小很多。尝试把c开根号看能否得到明文。一般的python开根号方法精度较低，对大整数开出来的根号准确度低。
发现使用gmpy2库可以对大整数开根号。
eg. RSA
已知:
e=2
c=9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
求明文m?
import gmpy2
import libnum
c = 9217979941366220275377875095861710925207028551771520610387238734819759256223080175603032167658086669886661302962985046348865181740591251321966682848536331583243529
m = gmpy2.isqrt(c)
m = int(m)
m_text = libnum.n2s(m) #将 十六进制转为 字符
print(m_text)
# flag1{Th1s_i5_wHat_You_ne3d_FirsT}
e=3 小明文攻击
适用情况：e较小，一般为3。公钥e很小，明文m也不大的话，于是m^e=k*n+c 中的的k值很小甚至为0，爆破k或直接开三次方即可。
eg . Jarvis OJ -Crypto-Extremely RSA
给了 flag.enc 和 pubkey.pem 文件
因为e=3，很可能存在小名文攻击，
可以假设，k为0，将 c直接开三次方就可以得到明文 m
Roll按行加密（加密是按行进行的）
eg . 实验吧---RSAROLL
ｎ为920139713
ｅ为19
首先把加密的部分另存为一份文件roll.txt
import gmpy2
from Crypto.Util.number import long_to_bytes
n = 920139713
p = 49891
q = 18443
e = 19
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = ""
with open('roll.txt','r') as f:
for c in f.readlines():
c = int(c)
#m += long_to_bytes(pow(int(c), d, n))
md = str(pow(c, d, n))
m += chr(int(md))
print(m)
#flag{13212je2ue28fy71w8u87y31r78eu1e2}
模不互素（存在两个或更多模数 n 且N1和N2不互质）
存在两个或更多模数，且gcd(N1,N2)!=1 也就是N1和N2不互质。
适用于，n超级大，用 yafu 的factor分解不了 的情况
N1 = 18674375108313094928585156581138941368570022222190945461284402673204018075354069827186085851309806592398721628845336840532779579197302984987661547245423180760958022898546496524249201679543421158842103496452861932183144343315925106154322066796612415616342291023962127055311307613898583850177922930685155351380500587263611591893137588708003711296496548004793832636078992866149115453883484010146248683416979269684197112659302912316105354447631916609587360103908746719586185593386794532066034112164661723748874045470225129298518385683561122623859924435600673501186244422907402943929464694448652074412105888867178867357727
e1 = 65537
message is 0x8BD7BF995BF9E16A0D04ADB49A2411C74FFDB0DB4F35DB3A79A1B44691947C9824085BC4CA5F7F4EFA3C8FD0BC3E870AA6D5E15307A63A2172C44C5903D35785B8D06B51651EE7106B070D5A6AABA089AB67609661265B74914C865F863DC1D2DC08CE0B026107A74EC3FDC62666B50110B9D15A243EAAD6F53646929A3369285404868E42DD0BBE92D956018E3C0B36EF5E9516E433228CFDD06D6E662EC0A9A31061EA11F61CA17EABF43D2D4977FC9D6FC53AB6DC01509401B8D9A46B59A9ADAA97D54CC50C27445E4C21B893510620EC3566AD6E8727FA147437B207505217E6F2DF009E2286C8354D281374D7802D08A2062FE48DBF135BBCAB120EBF84
N2 = 20071978783607427283823783012022286910630968751671103864055982304683197064862908267206049336732205051588820325894943126769930029619538705149178241710069113634567118672515743206769333625177879492557703359178528342489585156713623530654319500738508146831223487732824835005697932704427046675392714922683584376449203594641540794557871881581407228096642417744611261557101573050163285919971711214856243031354845945564837109657494523902296444463748723639109612438012590084771865377795409000586992732971594598355272609789079147061852664472115395344504822644651957496307894998467309347038349470471900776050769578152203349128951
e2 = 65537
message is 0x8C3CF3161AA3E37831030985C60566A7604688B73E5B1D3B36E72EF06ED4F71289EFE80E0D94BD755034E6C210F17DA85B9D0388F3AD104C68BC514A8EB1569A109EB5F266F7C5FA4DDFA638258949B43D4CF1406720CCD4CA11E74FDF8AEB35C56A79781C87157FC4213573329C5B0FF411F8A4F34580AA103DB9FD403C0D409FA11860A7C4595FDC49DC2CF94E5112B772E5DEC8F17E24B10A7FD7A95DCB87BE5E27C32FC931574A7847BC506A61EFE9DB3D3F612143845FE80D7B3EA548B886A67A29CBDB2775B1F91178B6DA763F1A6ECFF46592E4C7FFAAB6C9FEF29D9CB9E035A3D98ECFFB26BA2EEAA56D1CD096E6A2CF9A58086CAD7718DDA5CB0C1B
由于不能直接 分解 n ，只能先找出 n1，n2 的公因数作为 q ，再拿n1 ，n2 除以 q 得到 p1 和p2
然后在解密 ：
# python2
#!/usr/bin/python
#coding:utf-8
import gmpy2
from Crypto.Util.number import long_to_bytes
lines = open('tmp.txt','r').readlines()
c1 = int(lines[2],16)
c2 = int(lines[6],16)
n1 = int(lines[0])
n2 = int(lines[4])
p1 = gmpy2.gcd(n1, n2)
assert (p1 != 1)
p2 = n1 / p1
p3 = n2 / p1
e = 0x10001
d1 = gmpy2.invert(e, (p1 - 1) * (p2 - 1))
d2 = gmpy2.invert(e, (p1 - 1) * (p3 - 1))
m1 = pow(c1, d1, n1)
m2 = pow(c2, d2, n2)
print long_to_bytes(m1)+long_to_bytes(m2)
判定 x 和 y 是否互素：
#判断两个数是否互素
def gcd(a, b): # 判断来两个数是否互素,辗转相除法
if (b == 0):
return a
else:
return gcd(b, a % b)
def main():
x = 17 # x,y的值根据需要修改即可
y = 65537
if gcd(x, y) == 1: # 如果两个数的最大公约数是1，那么两数互素。
print(str(x) + " " + str(y) + " 两个数互素")
else:
print(str(x) + " " + str(y) + " 两个数不互素")
if __name__ == "__main__":
main()
共模攻击（m，n相同；e，c不同，且e1 和 e2互质）
适用情况：明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1也就是e1和e2互质。
对同一明文的多次加密使用相同的模数和不同的公钥指数可能导致共模攻击。
eg . Jarvis OJ -Crypto-very hard RSA
4096位的RSA加密，要不是这里存在共模攻击说不定你死活都解不开
题目给出了3个文件，其中2个明文是分开加密后的密文，另一个veryhardRSA.py则是加密脚本，我们通过分析加密脚本进而写出解密脚本。
查看加密脚本发现明文m、模数n相同，但是公钥指数e1和e2不同，而且e1与e2互素（上面给过判断2数是否互素的脚本）
python2:
import gmpy2
from Crypto.Util.number import long_to_bytes
e1 = 17
e2 = 65537
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
c1=int(open('./flag.enc1','rb').read().encode('hex'),16)
c2=int(open('./flag.enc2','rb').read().encode('hex'),16)
_, r, s = gmpy2.gcdext(e1, e2)
m = pow(c1, r, n) * pow(c2, s, n) % n
print long_to_bytes(m)
低解密指数攻击（e过大或过小，一般e过大时使用）
在RSA中d也称为解密指数，当d比较小的时候，e也就显得特别大了。
适用情况：e过大或过小（一般e过大时使用）
在e过大或过小的情况下，可使用算法从e中快速推断出d的值，进而求出m
eg . 我不是个人
n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597L
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619L
c = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
求明文m
然后把exp.py放入这个目录中运行即可（Python2 ）
#!/usr/bin/python
#coding:utf-8
import gmpy2
from Crypto.PublicKey import RSA
import ContinuedFractions, Arithmetic
from Crypto.Util.number import long_to_bytes
def wiener_hack(e, n):
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
frac = ContinuedFractions.rational_to_contfrac(e, n)
convergents = ContinuedFractions.convergents_from_contfrac(frac)
for (k, d) in convergents:
if k != 0 and (e * d - 1) % k == 0:
phi = (e * d - 1) // k
s = n - phi + 1
discr = s * s - 4 * n
if (discr >= 0):
t = Arithmetic.is_perfect_square(discr)
if t != -1 and (s + t) % 2 == 0:
print("Hacked!")
return d
return False
def main():
n = 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e = 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
c = 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
d = wiener_hack(e, n)
m = pow(c,d,n)
print long_to_bytes(m)
if __name__=="__main__":
main()
低加密指数广播攻击（模数n、密文c不同，明文m、加密指数e相同）
如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。
适用范围:
模数n、密文c不同，明文m、加密指数e相同。
一般的话e=k k是题目给出的n和c的组数。
eg . Jarvis OJ -2018强网杯nextrsa-Level9
题目给出
n1,n2,n3,
c1,c2,c3,
e,
求明文m的值。
python2
#!/usr/bin/python
#coding:utf-8
import gmpy2
import time
def CRT(items):
N = reduce(lambda x, y: x * y, (i[1] for i in items))
result = 0
for a, n in items:
m = N / n
d, r, s = gmpy2.gcdext(n, m)
if d != 1: raise Exception("Input not pairwise co-prime")
result += a * s * m
return result % N, N
# 读入 e, n, c
e = 3
n = [8564529398597496052509875513481234511905571293608253591774352345237876733293108831203723008958367224489489969614656703455962549261315442327443089652074571708651505447379309166100331065440172781968875497386410667715026180057913363208450111095566219238303387888025161407043477291378931412269049849744457547932264137377411127192940332805452317547219248055802197050456726624516860024108642571703812719370387292166670300197241575461417648592309869669813374010765766544607691011957968652581504886331252936146901456910589102484807039294566703917033093028140452849747910537865958098720693569821256189593894121111357731919189L,12222166297277342805260668042066733749258843622057497574551492680820573970618063356710810891221670366396148862070530068431772630271300064517141331380959413811482890080103511756363920299387620181525172247384085449944650678616398890947062703879307721506228672839270493453501648644787019360131991056158375296484870723717496184332078521221915234959627683952251865227849249752415242124235776428944052873501045127442031423538183282845800971359590735184850648986263721823804859410866927117413289461014754456802566932965710529063515405296476007642849800772934170961993925017146017197762805148533435040675962332469643915192423L,5057224034499776793532654516178914954537547410664409403680432108569079856741764362023185604595829263918927121465578691201904227912897025244771553860102714429349163283510695391193774853323951653123109509215361937850724934183826508070404239791710229214063382081391564954935544392514769166830815475459218792639383796711824752291158895292103354274632470559179266550681095452239666165213986993496109747058314685303485222302144835490056402939133225003233112131275635419321982899965440912525225759368684717157077161771778903529280898069381899400305195745292409238361901176051346615633641550303346790420492393767770845418243L]
c = [20010971557789931948130798983030201950038450269144104532821030667924400788869920238579729514672630221804096063149106742412869966814701225466606392171030411339119559280790040322081104363393453503417465768386174002015870794567148694722215873094298859132439253412531445187990845476275251348800166731481176155530755581153710085966976765505591809596417849783597055650440598035159288091495453205698044687869932756053447012994409598155552263807571713982758132066319612777306466708222135510918174055647735727504029507503430288609410745159037684948343055275573269067165460711584845480188706531450367147105629493736100726092945L,19200052919818196558567528701224082155105852846109782021681848107226495293687021416871117444987923837810238872836818190457667509409714021669160815809413653880491792640346474248859559867743715715552372738909255050196638006472279364316678941257894898953088366861786500472095752890593521428325838148184891778283229870316694059734109045397448347320487605412988229047015174998893589731503114337273121463601984792339337970193596813660178636222764332155999993506914518600565394196792457144962180040786607335687020278442899146954126853580244264273526509238060494624980807993322975135366653181977147866567146492356137019414255L,1394721540127922627584993749596603212491913755865039994631041458882716953251760080638497574652888386411767951258467542002582418260315909190241131591474627765734174146981015346732559115044918706641616288474447294129332475081232268241201488455865700933615291016346552048997127415783072860387265063527874160016186183078384940312292521628077750464413013768765371508493304331719166196330883242895556903378707199640686499970367957552543041110199009425369612644492288765891769004579050802446992426813215932250347386859783813875543314196764160792696291742850356532493945652482643696238487389412404616537620013009141601852080L]
data = zip(c, n)
x, n = CRT(data)
m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print m
eg . 存货6
题目给出n1,n2,n3,c1,c2,c3,e,求明文m的值。
# python2
#!/usr/bin/python
#coding:utf-8
import gmpy2
import time
from Crypto.Util.number import long_to_bytes
def CRT(items):
N = reduce(lambda x, y: x * y, (i[1] for i in items))
result = 0
for a, n in items:
m = N / n
d, r, s = gmpy2.gcdext(n, m)
if d != 1: raise Exception("Input not pairwise co-prime")
result += a * s * m
return result % N, N
# 读入 e, n, c
e = 9
n = [142782424368849674771976671955176187834932417027468006479038058385550042422280158726561712259205616626939123504489410624745195777853423961104590708231562726165590769610040722589287393102301338152085670464005026301781192671834390892019478189768725018303217559795377795540494239283891894830166363576205812991157L, 153610425077816156109768509904751446801233412970601397035720458311275245730833227428213917577405780162151444202393431444812010569489900435979730559895340377469612234558042643742219128033827948585534761030527275423811282367831985007507137144308704413007806012914286105842311420933479771294576841956749281552971L, 152540067782701001222493009941492423063369171831039847414320547494725020441901272486665728360741395415762864872737675660423920609681185809510355937534756399208661762715484879562585724584849261266873624875852300611683382543315580370484972470694466195837255994159609193239840228218925381488410059939975556977947L, 125842716702134814646356078531900645012495638692517778270527426844383063904041812273637776798591687732598509470005151551320457132061693618473039437320011446697406190781306264437609046721508738109650829547010385875425097336266103994639126319889016342284747700714199556143378526590058467791687837422897022829661L, 116144389285266462769913139639175922392318396923181100785008570884082681963637784423143843845816350379438789947802939701820129805341796427821894273985551331666719808355412080909245720551238149511778060242720419584504473490216670437024863860559347959698828131475160058721701582089480924088773887932997353631767L, 127833907448946785858374094953899556339175475846831397383049660262333005992005484987913355932559627279178940862787593749842796469355336182379062826441222705075178971785791223706944120681105575965622931327112817747065200324610697178273898956820957640413744954233327851461318200323486469677469950386824833536523L, 130561613227079478921314550968562766645507834694262831586725464124109153306162445639759476845681271537955934718244296904503168256991962908095007040044300188572466395275317838178325500238288302672390013747102961340256309124310478931896245221622317302428447389760864327859640573452084295225059466376349115703119L, 115953389401040751013569404909249958538962411171147823610874077094621794755967854844224923689925397631692572916641171075740839099217316101334941033937183815345038898177087515909675028366437302462022970987947264115373697445950951595479758872029099661065186221250394358255523574834723958546450323357472451930993L, 143437107845384843564651522639125300763388830136500260725097766445883003928355325003575359566631064630487365774344508496878731109174874449170057678821440711511966073934025028100604234445470976333825866939923998344367645612128590820812489407412175198698290167077116185959180877334222693344630253253476594907313L]
c = [85033868418784308573673709960700777350314426427677627319697346811123742342359072170220428874952996988431950989321281905284522596263957356289624365171732095210045916218066135140320107686084053271623461104022705353814233772164502775939590711842361956121603943483040254727995655776263673058788416722141673409688L, 66065963470666895005407449599703926269325406456711861190876894466341571726360462706664546294453572319565476664348345756905411939632955966517708138047546806602828064213238537646393524578984547577761559965654539771172357089802682793169968961304179886652390277814477825753096636750388350662980872556701402397564L, 116011740820520887443111656288411611070614127688662643257265381793048354928820176624229624692124188995846076431510548507016903260774215950803926107831505634778278712070141663189086436127990584944132764896694777031370995058271038329228336417590284517922855284619653301817355115583540545182119702335431334401666L, 97640420284096094887471273365295984332267897927392169402918423863919914002451127544715668846623138003564829254309568918651163254043205129883843425179687841236818720463784828905460885026290909768599562386370732119591181513319548915478512030197629196018254041500662654260834562708620760373487652389789200792120L, 8112507653841374573057048967617108909055624101437903775740427861003476480616929517639719198652146909660899632120639789106782550275648578142883715280547602249589837441805676364041484345030575130408744621981440093280624046635769338568542048839419939250444929802135605724150484414516536378791500915047844188300L, 36792148360808115566234645242678223867680969786675055638670907933041180936164293809961667801099516457636164692292891528415720085345494773373966277807505798679784807614784581861287048096977968620964436947452527540958289441390882589051225367658014709290392321808926567572528170531844664734909469690750971883323L, 53043093283305492238903255767698153246673671181809989362223466090875767705978690531154079519999671834688647277179370374802495005937892824566602423646978168777735383632928274082669949750078161820002768640908750005814934158829006019656592134357897586040866207754535586785064545866404380204728594863102313407789L, 88499407133762624445946519155722583633934260410706930537441122463087556094734626189377091740335667052378955691250910459790202385799502439716173363179773811920751410726795431402796346647688144853156900427797933862087074385441977254140336390678022955770879265490567987868532251217565094093318626424653599450992L, 138337520305048557335599940473834485492131424901034295018189264168040969172072024612859307499682986987325414798210700710891033749119834960687318156171051379643844580970963540418974136891389303624057726575516576726845229494107327508855516437230240365759885913142671816868762838801720492804671259709458388192984L]
data = zip(c, n)
x, n = CRT(data)
m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits()
print long_to_bytes(m)
#Tr0y{e=3_1s_danger0us!}
