六月作业

*RSA File

1
2
3

with open("pub.key","r",encoding="utf-8") as file:
    text=file.read()
key=RSA.import_key(text)

在线网站

只有0到4？

广播攻击

from sympy.ntheory.modular import crt
from gmpy2 import iroot
from Crypto.Util.number import *

e = 3
n1 = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c1 = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

n2 = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c2 = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

n3 = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c3 = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

n1 = int(str(n1), 5)
c1 = int(str(c1), 5)
n2 = int(str(n2), 5)
c2 = int(str(c2), 5)
n3 = int(str(n3), 5)
c3 = int(str(c3), 5)
N = [n1, n2, n3]
C = [c1, c2, c3]

resultant, mod = crt(N, C)
value = iroot(resultant, e)[0]
print(long_to_bytes(value))

另一种方法

for i in range(len(n)):
    for j in range(len(n)):
        if i != j:
            if gmpy2.gcd(n[i], n[j]) != 1:
                print(i, j)  # 输出对应的n的序号
                p = gmpy2.gcd(n[i], n[j])
                print("p = ", p)
                q = n[i] // p
                print("q = ", q)
                d = gmpy2.invert(e, (p - 1) * (q - 1))
                print("d = ", d)
                m = pow(c[i], d, n[i])
                print("m = ", m)

两个n有公因子，直接求解

RSA？

直接爆破m

from Crypto.Util.number import *
import gmpy2

c1= 47916081717706538925639104682570684180170502544820197539239827441426724468768104306254078605230687136184497929
n1= 164133678169710886720989064489094710242148933867688762980230890673424334054283751851389412792855634009922402873730095480540590589967587744481839586009206921690415208556737311431588106941893527836076971942678255228990259381439694065742253470463684082142779114879828632048097049587164541575068678559785497341341
c2= 63878844405215916614306503133484342687866237414982537489487243642156715327887644418701791728466044672606833177790745723348407141495434918350324367721472060206442057535810542180796122799773614557047720846326110736372382283280049448530028736552356917154044523343646598823659486063811304671208433254991406080968
n2= 81943314005002234143294576769951701354140501422348161833411886396153974002840590020014331444356263770668675416273077939014396178809052011274358602695903955726427501943378842406211922876951617483948075311923120200295968581991729752554553727773176109055672586268192629406914315361730879469185143748796847985621
e2=3
k=0
while(gmpy2.iroot(c2+k*n2,e2)[1]==False):
    k+=1
#print(k,c2+k*n2,gmpy2.iroot(c2+k*n2,e2)[0])
#m2=3997474330692954004892367968364354963663898428651951374234371210083046726737590992626245650194376316882
e1=2
k=0
while(gmpy2.iroot(c1+k*n1,e1)[1]==False):
    k+=1
#print(k,c1+k*n1,gmpy2.iroot(c1+k*n1,e1)[0])
m=6922144300555033858896226859793246979270479673047458173
flag=long_to_bytes(m)
print(flag)

Break_RSA

from sage.all import *
from Crypto.Util.number import *
n = 25348605574630284342864323710011622959543974652863854537355760576386763162531478272446867731299572532294812374775121121761898206639041068156270466457595336452690367719842145233764550634280981441631262047763246059814963741143303914063537003244814908763379320576260885158458898112416692583017869283284022878603506583499699525249773663841642694427307104140944360804367072787670581252816486834658346431010523135392357008103555699542414687172408709153334263858639251735462278292703380745537045458408951791720967957274781161667526873251066303708008043058246747534357368350540174588670636827470901518225473676343782182718627
p4 =0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000 
e = 0x10001
pbits = 1024
for i in range(0,4096):
    p4=0x3e67e7cacd2584224fb2026b40afbcc4281bd59f72f7801239d95c61c48ded7649924f794592fce806e032f16c2f4a90466905fc30037317074a6424d8bf078e959a1ed2d8e5c000
    p4=p4+int(hex(i),16)
    kbits = pbits - p4.nbits()
    p4 = p4 << kbits
    PR.<x> = PolynomialRing(Zmod(n))
    f = x + p4
    f = f.monic()
    roots = f.small_roots(X=2^kbits, beta=0.4)
    if roots:
        p = p4+int(roots[0])
        print( "n: ", n)
        print("p: ", p)
        print ("q: ", n//p)
        break
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)   
print(long_to_bytes(pow(c, d, n)))

\[ 模数为N,N具有一个因子b>=N^β, 0<β<=1. \]

Coppersmith method主要通过LLL方法找到与该多项式具有相同根x0，定义域为整数域的多项式g，即可求解。

LLL算法

LLL算法的目标是找到一个向量空间的近似最短正交基。LLL的约化过程，是先约化前k个基，然后拓展到k+1个基，最终完成全部n个基的约化过程。因为近似最短，所以该算法可求解部分SVP问题，进而求解coppersmith问题。

babyrsa

from Crypto.Util.number import *
import gmpy2

p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
enc = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
mod = pow(2,265)
p0 = n * inverse_mod(q_low,mod) % mod
PR.<x> = PolynomialRing(Zmod(n))
for i in range(2**5):
    f = p_high * (2^724) + p0 + (x * 32 + i) * mod
    f = f.monic()
    out_p = f.small_roots(2^454,0.4)
    if len(out_p) != 0:
        print(out_p[0])
        break
p = out_p[0] * 32 + i * mod + p_high * (2^724) + p0
# print(p)
p = 133637329398256221348922087205912367118213472434713498908220867690672019569057789598459580146410501473689139466275052698529257254973211963162087316149628000798221014338373126500646873612341158676084318494058522014519669302359038980726479317742766438142835169562422371156257894374341629012755597863752154328407
assert n % p == 0
q = n // p
fai_n = (p-1) * (q-1)
d = inverse_mod(e,fai_n)
m = pow(enc,d,n)
print(bytes.decode(long_to_bytes(m)))

q_low可以通过n逆到p_low，通过small_roots求解

Wiener’s Attack

连分数定理 \[ 当|x−\frac{a}{b}|<\frac{1}{2b^2}时，\frac{a}{b}是x的一个连分数近似。 \] 用t和_n能求出u，但是在求u的过程中可求p和q。

求出e1后，e1和e2可以用扩展维纳求解m。

扩展维纳

\[ g = gcd(p-1, q-1) \\ ed = 1 + k(p-1)(q-1)\\ edg = g + k(p-1)(q-1)\tag{1} \]

\[ e_1d_1 = 1+k_1\phi(N)\\ e_2d_2 = 1+k_2\phi(N)\\ e_1d_1k_2-e_2d_2k_1=k_2-k_1\tag{2} \]

从而可得 \[ A*L=B\\ A=(k_1k_2,d_1gk_2,d_2gk_1, d_1d_2g^2)\\ L=\begin{bmatrix} 1&-N&0&N^2\\ 0&e_1&-e_1&-e_1N\\ 0&0&-e_2&-e_2N\\ 0&0&0&e_1e_2 \end{bmatrix}\\ B=(k_1k_2,k_2(g+k_1s),g(k_1−k_2),(g+k_1s)(g+k_2s)) \] L为格基，若B为最短向量可用LLL求解。 \[ 只有满足\lambda_1(L)\le\sqrt{N}det(L)^\frac{1}{n}才是最短向量。 \] 现成的格子： \[ M_1=N^{0.5}, M_2=N^{1+\alpha},\\ L第一列乘N，第二列乘M_1, 第三列乘M_2,得\\ L_2=\begin{bmatrix} N&-M_1N&0&N^2\\ 0&M_1e_1&-M_2e_1&-e_1N\\ 0&0&-M_2e_2&-e_2N\\ 0&0&0&e_1e_2 \end{bmatrix}\\ B=(k_1k_2N,k_2(g+k_1s)M_1,g(k_1-k_2)M_2,(g+k_1s)(g+k_2s))\\ 所以||B_2||\le2N^{1+2\alpha}\le\sqrt{N}det(L)^\frac{1}{n}=2N^{\frac{1}{4}(\alpha+\frac{13}{2})}\\ 求得\alpha\le\frac{5}{14}.\\ 然后可以将\alpha带入M_2用LLL求最短向量B_2，右乘L_2的逆求A，由A的前两项求解。 \]

from Crypto.Util.number import *
from gmpy2 import invert

c = 6472367338832635906896423990323542537663849304314171581554107495210830026660211696089062916158894195561723047864604633460433867838687338370676287160274165915800235253640690510046066541445140501917731026596427080558567366267665887665459901724487706983166070740324307268574128474775026837827907818762764766069631267853742422247229582756256253175941899099898884656334598790711379305490419932664114615010382094572854799421891622789614614720442708271653376485660139560819668239118588069312179293488684403404385715780406937817124588773689921642802703005341324008483201528345805611493251791950304129082313093168732415486813
e2 = 27188825731727584656624712988703151030126350536157477591935558508817722580343689565924329442151239649607993377452763119541243174650065563589438911911135278704499670302489754540301886312489410648471922645773506837251600244109619850141762795901696503387880058658061490595034281884089265487336373011424883404499124002441860870291233875045675212355287622948427109362925199018383535259913549859747158348931847041907910313465531703810313472674435425886505383646969400166213185676876969805238803587967334447878968225219769481841748776108219650785975942208190380614555719233460250841332020054797811415069533137170950762289
e1 = 114552459553730357961013268333698879659007919035942930313432809776799669181481660306531243618160127922304264986001501784564575128319884991774542682853466808329973362019677284072646678280051091964555611220961719302320547405880386113519147076299481594997799884384012548506240748042365643212774215730304047871679706035596550898944580314923260982768858133395187777029914150064371998328788068888440803565964567662563652062845388379897799506439389461619422933318625765603423604615137217375612091221578339493263160670355032898186792479034771118678394464854413824347305505135625135428816394053078365603937337271798774138959
N  = 14922959775784066499316528935316325825140011208871830627653191549546959775167708525042423039865322548420928571524120743831693550123563493981797950912895893476200447083386549353336086899064921878582074346791320104106139965010480614879592357793053342577850761108944086318475849882440272688246818022209356852924215237481460229377544297224983887026669222885987323082324044645883070916243439521809702674295469253723616677245762242494478587807402688474176102093482019417118703747411862420536240611089529331148684440513934609412884941091651594861530606086982174862461739604705354416587503836130151492937714365614194583664241
a  = 0.356#731./2049
M1=N**0.5
M2= N **(a+1)
D = diagonal_matrix(ZZ,[N,M1,M2,1])
M=matrix(ZZ,[[1,-N,0,N**2],[0,e1,-e1,-e1*N],[0,0,e2,-e2*N],[0,0,0,e1*e2]])*D
L=M.LLL()
t=vector(ZZ,L[0])
x=M.solve_left(t)
print(x)
phi = int(x[1]/x[0]*e1)
d = invert(0x10001,phi)
m=pow(c,d,N)
print(m)
print(long_to_bytes(9082754779802416065229245885387712939943943582794993779715278978532329981453479995551082109))
'''
g = gcd(p-1, q-1)
矩阵A等于[k1k2, d1gk2, d2gk1, d1d2g^2] 即为x
'''

xor_1

def get_pq(n, x):
    a = [0]
    b = [0]
    maskx = 1
    maskn = 2
    for i in range(1024):
        xbit = (x & maskx) >> i
        nbit = n % maskn
        t_a = []
        t_b = []
        for j in range(len(a)):
            for aa in range(2):
                for bb in range(2):
                    if aa ^ bb == xbit:
                        tmp2 = n % maskn
                        tmp1 = (aa * maskn // 2 + a[j]) * (bb * maskn // 2 + b[j]) % maskn
                        if tmp1 == tmp2:
                            t_a.append(aa * maskn // 2 + a[j])
                            t_b.append(bb * maskn // 2 + b[j])
        maskx *= 2
        maskn *= 2
        a = t_a
        b = t_b
    for a1, b1 in zip(a, b):
        if a1 * b1 == n1:
            return a1, b1

每一位异或都有四种情况（00,01,10,11）通过n的低位可以约束这四种情况，从低位到高位依次遍历可解。

RSAOS

普通指令先CRC签名再RSA签名，特权指令先foldhash签名再RSA签名。当enable打开时，普通指令也需要foldhash签名。

foldhash实现

1 2	sha1_s = sha1(s).digest() return bytes(x ^ y for x, y in zip(sha1_s[:10], sha1_s[10:]))

由于程序的判断条件，指令后可以跟其他字符，签名时是签一整个指令。

然后便可以找到多个CRC的签名使之乘积等于get-flag的foldhash签名，又由于RSA的乘法同态，最后签名得出的结果是一样的。

于是就可以CRC求逆，每个foldhash的因子不应该超过CRC32要求的32位。可选择get-flag 999。