2022年 HSC-1th中CRYPTO的BABY-RSA
照例下载附件，是 py 文件：
from Crypto.Util.number import *
def lfsr(status,mask):
out = (status << 1) & 0xffffffff
i=(status&mask)&0xffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
out^=lastbit
return (out,lastbit)
status= 1
mask = 0b10110001110010011100100010110101
num = bytes_to_long(m)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
hp = bin(p)[2:]
c = pow(num, e, n)
print("n=",n)
print("c=",c)
f=open("key","w+",encoding='utf-8')
for i in range(568):
curnum = int(hp[i])
(status,out)=lfsr(status,mask)
f.write(str(curnum ^ out))
f.close()
'''
n= 9363543374665338283861145656340115756598328744870620756798779080826725774691364161648335378062705433999048117564356637094421930886166369832353405527855104576202658647651524758179962855692461154859961903531990172279764099199157181167775307950690492969859829926808950964120678082460448847927074487568619536568740301649988555476490206693181162301088156855926656544441682939839165455244630182978802660669255401576213941067679888164237586879364615664942234247896214195262510935345922512831632385741735810122730130366521612834556565838623708828780093323310348242654778247293430853566054703991781432542625271396246500576703
c= 3641304537029815746727163894554557322382012539953948183406308231174259571263608621970973671202001456955622458371303424750815017578104069924877881162707673935496925529412748663209884628320657034190702348924814794263041483260377960569530869386619921425415323912964305979776909598200202236912823968867485696101691879580799000240715778010424877093758489309380968229017074542588151574195295436881889313935734282141447498134543053106463951864974512375314091440713165047188590693431938599822340588934591712592995622334522799914563528630705687647950894928965913199772209825508001274120556508220248069647851360567609656517789
'''
.
.
一看 lfsr 我开心了一下，我研究过这个：
https://blog.csdn.net/xiao__1bai/article/details/120392307
后来又哭了，果然还是研究得不透彻，稍微变一下式就卡住了，就那里怎么求出原来的 out 就想了很久~
后来在不断尝试后逐渐有了思路 lfsr 加密函数中传入的两个参数 status,mask 都是固定的，那么 return (out,lastbit) 不也是固定的吗？这样就可以求出原来的 out 了啊!
from Crypto.Util.number import *
#这里只取out即可
m = open("flag.txt","rb").read()
def lfsr(status,mask):
out = (status << 1) & 0xffffffff
i=(status&mask)&0xffffffff
lastbit=0
while i!=0:
lastbit^=(i&1)
i=i>>1
out^=lastbit
return (out,lastbit)
status= 1
mask = 0b10110001110010011100100010110101
num = bytes_to_long(m)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 65537
hp = bin(p)[2:]
c = pow(num, e, n)
#print("n=",n)
#print("c=",c)
#print("hp=",hp)
f=open("key","w+",encoding='utf-8')
for i in range(568):
curnum = int(hp[i])
(status,out)=lfsr(status,mask)
print(out,end='')
f.write(str(curnum ^ out))
f.close()
'''
out=
1101110101011011011111100001101100111111101100000010011101001110101101011110000100001110111110010000000010111110011001011000110010100101100001001111011110010000011011001010110001100000111110001111110001010101001101011110011110000100110100110000110011001101010100111000100000100110010010011001110000010110010110100101101100100111000011010100001000101010000111001000010110101110000000010101011000011111110001001111110010100011000100111010000010010110001000101111001000000100100011001010111110110100001001001000000100100101111111101000000011000100001001100001011010010010
'''
.
.
用上面的结果再异或回结果 key，就能得出 568 位的 curnum ，这就是 RSA 关键参数 P 的一部分啊：
out=list("1101110101011011011111100001101100111111101100000010011101001110101101011110000100001110111110010000000010111110011001011000110010100101100001001111011110010000011011001010110001100000111110001111110001010101001101011110011110000100110100110000110011001101010100111000100000100110010010011001110000010110010110100101101100100111000011010100001000101010000111001000010110101110000000010101011000011111110001001111110010100011000100111010000010010110001000101111001000000100100011001010111110110100001001001000000100100101111111101000000011000100001001100001011010010010")
#out输出与RSA无关
key=list("0101110100100111011011011000111010000111101000101010100100100011010111011000010010100101110110011101110110010100010111001110010011101010111011001100011011010110001010011111111110100110101010101110100110011010110101110110000110010101010000010110100110110110001110101011000011110100011011100101101101001000110010100111000111001111010101011011111110010111100101111001010000100010100001000111010011011111010011101100011101011010011010110001101110110110000110010011001101100000110000110100101010010010110101100101111101110000010011101110010101110100011101100110111111001010")
for i in range(568):
print(int(out[i])^int(key[i]),end='')
#hp=list("1000000001111100000100111001010110111000000100101000111001101101111010000110010110101011001000001101110100101010001110010110100001001111011010000011000101000110010001010101001111000110010100100001010111001111111000101000011000010001100100100110010101111011011010010011100011010010001001111100011101011110100100000010101011101000010110001111110110111101100010110001000110001100100001010010001011000000100010100011101111111001011110001011101100100000001110111100000101100100010011111110010100100110111100101101111001010101101100000110010110110000010100000111100101011000")
.
.
然后继续用关键字查资料，发现 568 位可以实现 RSA 高位攻击，恢复 P：
相关的脚本一大堆：https://www.jianshu.com/p/e407be39a22b?from=singlemessage
由于没下sage，用在线网址：https://sagecell.sagemath.org/
.
.
一开始直接用别人的脚本发现很多错，后来发现是sage语法变了，print要加括号了：
from sage.all import *
#n = 0x9d3a1a28ecb1bd245dd86b18dc4c5b729f23778710005118836129f08e31d6516de8ab47db1b3b7f660f50d283b1e9f2c06e7836136e4c0159f5d2b05771861d3ce6aa8715932eadc1cc0f380909a1961018340f7393142f9c177b1187151f97ac8cdc4ad17fa59a0f39d192af555f27de9cc800846eb2ca6ce78f87c0c0fbf47828328392b81771af624389fd779d130d80739bb7a608961125ba3f1800c766440fa70bfd3f834294d47d7ed9cfffd6d14ae18310f6c1d6d8f88b6c5d72a0b45608b4e21bbb8e314220ed7a2d6a8c95454e571c71b50f1d6a823778ca47131f5b889a1ed1957248bee8c4ac66872a5fd58a121560a27bad4958f1c763f2ffddL
n = 0x4a2c6dd9af83d8cc06b4e721475e9d8a9bce1de6ddd43be7658f13bb5c5b452e9f42d9d77b8c5c3e50ef64e0edc524903e8ee759d805a63cfe613ec022115d54e73724ced3bfff73e1872b7b35b040537f8ac89523d9e2860199d6d0b1c4d7830ee5b468bd7406990ffa29caa2d8fad285b3dba209b34b427d749d7e2aebded78f49e5017bfeec1cb9f72e63506d82af561a4858f652d3fb152526c10c7e4c5e15c84803efac675fb9297d915bd1e2eda5a5de3d48bbf68380303e0d8de81704fff8c9f07ae4d15212b9066227583345425ba7a04e06fd0c16ec6bfdd764318587d1bfe76a9834043b16392018e192456cb3ea994d2a187cabfa706efbee8dbfL
#p4 =0x807c1395b8128e6de865ab20dd2a39684f6831464553c65215cfe2861192657b6938d227c75e902ae858fdbd8b118c8522c08a3bf978bb203bc1644fe526f2de55b065b050795800
#最后面8位二进制，也就是两位十六进制要参与爆破运算，所以要用 00 补充
e = 0x10001
pbits = 1024
for i in range(0,256): # 要爆破的8位二进制数，为2**8=256，表示0~255
#p4 =0xda5df16f286dbc825cd0c8ee48aa26ac27338a75172c5b92351f14d083216f7e91b9355e27cf930646fbbda6058dec3c4ddf751f36df5556359fbe671f9b947b4c79cadfdbb27b00
p4 =0x807c1395b8128e6de865ab20dd2a39684f6831464553c65215cfe2861192657b6938d227c75e902ae858fdbd8b118c8522c08a3bf978bb203bc1644fe526f2de55b065b050795800
p4=p4+int(hex(i),16)
# print hex(p4)
kbits = pbits - p4.nbits()
# print p4.nbits()
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
#经过以上一些函数处理后，n和p已经被转化为10进制
if roots:
p = p4+int(roots[0])
print ("n: ", n)
print ("p: ", p)
print ("q: ", n/p)
break
.
.
得出 n、p、q 后直接常规解密即可：
import libnum
from Crypto.Util.number import long_to_bytes
p = 90225006288627020933267024425797647042965554486273674145474629022335483579168020321334177600624475358419458781387021577078957978886555066264514364951229871833611713144617155837023313756741716041993159155093522769416742461683810041045361926334946115547487234272520914249496954864904467634471167509689549908477
q = 103779913793651074214263503010594071424969073353841622604658974812940029980624584116398305918269283126971163279620945190907582597922068185151061264528002313474791985042185827606404465614715082278876591600452809285354307582767265999134237277732506671463834101956213961309366951706106789005830772784151863039339
n = p * q
e = 65537
c=3641304537029815746727163894554557322382012539953948183406308231174259571263608621970973671202001456955622458371303424750815017578104069924877881162707673935496925529412748663209884628320657034190702348924814794263041483260377960569530869386619921425415323912964305979776909598200202236912823968867485696101691879580799000240715778010424877093758489309380968229017074542588151574195295436881889313935734282141447498134543053106463951864974512375314091440713165047188590693431938599822340588934591712592995622334522799914563528630705687647950894928965913199772209825508001274120556508220248069647851360567609656517789
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n)
string = long_to_bytes(m)
print(string.decode())
.
.
解毕！
敬礼！