0%

RSA题型总结

Crypto_easy_crypto | N中有大合数

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from Crypto.Util.number import *
from secret import flag

def keygen(nbit):
while True:
p, q, r = [getPrime(nbit) for _ in range(3)]
if isPrime(p + q + r):
pubkey = (p * q * r, p + q + r)
privkey = (p, q, r)
return pubkey, privkey

def encrypt(msg, pubkey):
enc = pow(bytes_to_long(msg.encode('utf-8')), 0x10001, pubkey[0] * pubkey[1])
return enc

nbit = 512
pubkey, _ = keygen(nbit)
print('pubkey =', pubkey)

enc = encrypt(flag, pubkey)
print('enc =', enc)
#pubkey = (763929224901239050077647342425144363318006219360210465113458622937882119766705458273788947718911994090187932947694326848868575500906975653763043489419853300731695950407389203582333794360159494405111004208058198680365172060235321945875374635278292661761319773173838900295933943437761251440819434675631450032782188481758975272071015244168751016874668742536151359822585793537758876078350987062972237271763834743266722655055439868971805843593929839097963319788083763,
# 27750416681837900468631425875797804482827864226099175414717825894823303299159277202974070903630276868248755642608884903122768656427165401563920443482151217)
#enc = 7579294603035135817234501131256282324240132424272000903035801073847222917306092792610406876451698121956232047031639448767323475088170357863653435096746640609325525035329328626562143049656124241263576649974820533800161432666946327226418036826146160288273175521864687122720836795596635067761146519940441817765732160382018434465776749372209181212817247187474685246156193381822044772746654690126746715728166527274933634750443478682812664022009444348448955720226579468781927776133336045525149203384137859868153077820708167146052429014790660921586958660759949399826568136755816563468739111123761288318276379025018708883521

题解

1
2
3
4
5
6
7
8
9
import libnum
b=27750416681837900468631425875797804482827864226099175414717825894823303299159277202974070903630276868248755642608884903122768656427165401563920443482151217
c=7579294603035135817234501131256282324240132424272000903035801073847222917306092792610406876451698121956232047031639448767323475088170357863653435096746640609325525035329328626562143049656124241263576649974820533800161432666946327226418036826146160288273175521864687122720836795596635067761146519940441817765732160382018434465776749372209181212817247187474685246156193381822044772746654690126746715728166527274933634750443478682812664022009444348448955720226579468781927776133336045525149203384137859868153077820708167146052429014790660921586958660759949399826568136755816563468739111123761288318276379025018708883521
e = 0x10001

phi = b-1
d = libnum.invmod(e, phi)
flag = pow(c,d,b)
print(libnum.n2s(flag).decode())

直接把另一堆(p*q*r)忽略了,当成单素数(p+q+r)加密的RSA解🤔

回想起来,原来看过此类问题的解法视频

可惜,被p、q、r唬住了。

结论

  • N分解过程中,比m大的合数可以直接忽略
    • 剩下的也不一定是素数,记得check
    • 剩下的数当作新的模,得大于m(不然就得爆破k)

为什么?不知道

CRT | 共d

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
from Crypto.Util.number import *
import gmpy2
from random import shuffle

flag = b"flag is here"


def shuffle_flag(s):
str_list = list(s)
shuffle(str_list)
return ''.join(str_list)


nl = []
el = []
count = 0
while count != 5:
p = getPrime(512)
q = getPrime(512)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.next_prime(bytes_to_long(flag))
e = gmpy2.invert(d, phi)
nl.append(n)
el.append(int(e))
count += 1

print(nl)
print(el)

cl = []
flag = shuffle_flag(flag.decode()).encode()
for i in range(len(nl)):
cl.append(pow(bytes_to_long(flag), el[i], nl[i]))
print(cl)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
###Sage###
from gmpy2 import *
import libnum
nl=[92568419674731290088321621356482160506897805615722568594108449347104924357404183476911642777855820991398881156764068184840768873749718093598712551142529474514837161712525386555067489900887826033760157015587905876891826276883359425048106383489316555600680137377034136599761900203863336332834524981581608546277, 156396473818563541024482014372866929605198443382524196879362284224099117401220679011156723462510565131555949471059964179767945960498473012008220045105490122503438703770112687917922899337041421537937431868908340506324082719417747902320117904166584374628828367801012533926776313544525573302674702867896838756349, 158394833243620345170313957479796081390446308753163267294427471181012679879060921676287361174926310080500003540773261012005682050743188110335872216992843352902160171999286576526304619756655278142788064189969927027027650043645613441449926633380809295720977302961310978360575684689811662689798196832145977450067, 160088237013152996062303719345275590040820298863729670660621544625451638541931139026114480452748397901155923890465415946150076272684251867169893163248736673419035618274961179288085209456220719404244194802327491684233804878013160262798831738441790443743813368173495029170393018727204042599457829167334217403039, 176125361422384852665447804150030174008849487020728296169340093618559367127086381778331613043595010796295772394708222184703701230685609172767761426620379001062695169120599393984950488304290958534830276649464003949555105491117656796777657620812669612752464591728873199832200616338112460100967288829163217253937]
el=[69312028009355287369151190914681978515224902099126626288106202481561083869512381976466800912049172557479956400189281179789850182367192324370292880508005951892909864237831856642160554901550928757105750738313195248541515727624216048436593804176317465366380022764459799506858495981817822670957526705611211712923, 75652848678989239962391202584125835503829570694373189157636155436633908234362973839251550542975725789188895010096917574118924190081886365041870173203566890015476761857546914959928731140619341634983144909962106759048918025248827973161384045263311189477657141886093632791593341193393085433749877270828641736687, 33787880341418355427411601538315129862488529656310145182009801227014512555036822623215545927750632031483856865027938518144081751233475248361490189179988637342429805607352670543555743822390555949569061340741015073482051059972283793490798701339277926430357560613555427570475360496737455291914090967005368044847, 45894271603047945281790624112313938740541711331584775481261776728213544262108835859642003140814571796838418889270625806159755478669858113687476417240730385707171289922064965084283027730393146219788228689778873266618663473231744646293406030907691363263939114550226424730102211751706087680590823466426973879111, 39462780066564051085365889083337472288277223628014907704844994419242541623368920096395581667207909872944692627394665038729398405841875334128211337544205143876652949004817962123951132753801707134333132359039376283331685997619531570270269964807335633423631078057345827010794671894948828680193958561375351954627]
cl=[706565317398633346290694952311166623770389747503953970254889622211015097472765489676349936599997109100148837713409666075736711752497174928509516666210124850782396573268200919345005742905131769799719677758163730270857245509037860252700476102090438501579886321486095767737006847692632649652528793934802014895, 39976293505792731417500342473259466413746324373570160856607039564687056797068114044891309890160001547746290678089875953230720229396293686037539133378586045964793387433679304899158546834837314101138069400994334720071006048815998660691472991971598192116289517127819703723844842002711298154106615035755646791235, 82622936948791971063481195310587447614375265630407688161651173440160941964839173273115526802240672776681580169092371677673709037579318090622040018030730165371997331146171751228791524747622285256591779419274845659567001522182995468819720594650389854677582186770321424062935881407083956991646633760500152137305, 47924672523033740219454774309397006543851002473271747603676349322670782245519637286314088457132590816165876451615235937683074852920250584155682791595116359054889940842281324709426616771765312825842634237678243213350551342690870568516232078792788925700389762945955053433276153136302757700081859531596237286407, 157462720644970256050843434459828247139256140406409429896418317109064365936294939244159292550184482469972819258184119865598346921909220060266145241164734603316978286567811044606538176157224828857158099074286931716459626013079677895357212211176535500327064375073662684801175545519382470886239209020257096407424]

M=iroot(int(nl[4]),int(2))[0]
a=[0]*6
a[0]=[M,el[0],el[1],el[2],el[3],el[4]]
a[1]=[0,-nl[0],0,0,0,0]
a[2]=[0,0,-nl[1],0,0,0]
a[3]=[0,0,0,-nl[2],0,0]
a[4]=[0,0,0,0,-nl[3],0]
a[5]=[0,0,0,0,0,-nl[4]]

Mat = matrix(ZZ,a)
Mat_LLL=Mat.LLL()
d = abs(Mat_LLL[0][0])// M # 这里得是整除 ‘//’ !!!
d= int(d)
while not(gmpy2.is_prime(d)):
d -= 1
flag = int(d)
print(libnum.n2s(flag).decode())

或许非预期吧,直接把d用LLL算法求出来了。

结论

  • 共d用LLL算法攻击(记得d = abs(Mat_LLL[0][0])// M整除!

crtrsa | dp小,e 很大

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from secret import flagn,p,q
#p and q are two primes generated by getPrime
import random
def key_gen():
while True:
dp = random.randint(1,1<<20)
dq = random.randint(1,q-1)
if gcd(dp, p - 1) == 1 and gcd(dq, q - 1) == 1:
d = crt([dp,dq],[p-1,q-1])
phi = (p-1)*(q-1)
R = Integers(phi)
e = R(d)^-1
return p*q,e
n,e = key_gen()
print e
print n
print pow(flagn,int(e),n)

'''
e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
N = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
flag = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399
'''

可以看到dp的范围是在[1,1048576],这个范围应该是可以进行穷举的 -> dp已知

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import gmpy2
from Crypto.Util.number import *

e = 2953544268002866703872076551930953722572317122777861299293407053391808199220655289235983088986372630141821049118015752017412642148934113723174855236142887
n = 6006128121276172470274143101473619963750725942458450119252491144009018469845917986523007748831362674341219814935241703026024431390531323127620970750816983
c = 4082777468662493175049853412968913980472986215497247773911290709560282223053863513029985115855416847643274608394467813391117463817805000754191093158289399
#dp = d % (p-1) dq = d % (q-1)

m = 10000001
for dp in range(1,(1<<20)+1):
print(dp)
temp = pow(m,e*dp,n) - m
p = gmpy2.gcd(n,temp)
if p != 1:
q = n // p
try:
d = gmpy2.invert(e,(p-1)*(q-1))
flag = long_to_bytes(pow(c,d,n))
if b'flag' in flag or b'ctf' in flag:
print(flag)
break
except:
pass


#dp = 915155
#b'flag{d67fde91-f6c0-484d-88a4-1778f7fa0c05}'

总结

因 e⋅dp≡1(mod(p−1)),又由费马小定理,对r (大于1的整数 且 gcd(p, r)=1),有 $r^{e⋅dp} ≡ r (modp)$,即 $p | (r^{e⋅dp} − r)$;

又 p | n,很大概率 $p=gcd(r^{e·dp} − r, n)$

  • 当dp较小且已知,e又较大时,对任意 m$p=gcd(r^{e·dp} − r, n)$

Easy_Rsa | p-1、q-1有公因子

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from Crypto.Util.number import *
from flag import flag
import gmpy2

def gen_prime(nbits, gamma):
g = getPrime(int(nbits * gamma))
alpha = 0.5 - gamma
while True:
a = getRandomNBitInteger(int(alpha * nbits))
p = 2 * g * a + 1
if isPrime(p):
b = getRandomNBitInteger(int(alpha * nbits))
q = 2 * g * b + 1
h = 2 * g * a * b + a + b
while not isPrime(q) or isPrime(h) or gmpy2.gcd(a, b) != 1:
b = getRandomNBitInteger(int(alpha * nbits))
q = 2 * g * b + 1
return p, q

def encrypt(nbits, gamma):
p, q = gen_prime(nbits, gamma)
n = p * q
e = getPrime(16)
while gmpy2.gcd(e, gmpy2.lcm(p-1,q-1)) != 1:
e = getPrime(16)
m = bytes_to_long(flag)
c = pow(m, e, n)
return n, e, c

n, e, c = encrypt(1024, 0.48)
print 'n =', n
print 'e =', e
print 'c =', c

# n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
# e = 58337
# c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Pollard’s rho
def f(x, n):
return (pow(x, n - 1, n) + 3) % n

def rho(n):
i = 1
print('Factorizing')
while True:
x1 = getRandomRange(2, n)
x2 = f(x1, n)
j = 1
while True:
p = gmpy2.gcd(abs(x1 - x2), n)
if p == n:
break
elif p > 1 and isPrime(p):
print('Found!')
return (p, n // p)
else:
x1 = f(x1, n)
x2 = f(f(x2, n), n)
j += 1
i += 1


n = 84236796025318186855187782611491334781897277899439717384242559751095347166978304126358295609924321812851255222430530001043539925782811895605398187299748256080526691975084042025794113521587064616352833904856626744098904922117855866813505228134381046907659080078950018430266048447119221001098505107823645953039
e = 58337
c = 13646200911032594651110040891135783560995665642049282201695300382255436792102048169200570930229947213493204600006876822744757042959653203573780257603577712302687497959686258542388622714078571068849217323703865310256200818493894194213812410547780002879351619924848073893321472704218227047519748394961963394668

p, q = rho(n)
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m = pow(c, d, n)
print(long_to_bytes(m))

# Factorizing
# Found!
# b'SangFor{0a8c2220-4c1b-32c8-e8c1-adf92ec7678b}'

总结

Common Prime RSA

情形:gcd(p−1,q−1)=g

分解的n方法有四种:

(1)修改Pollard’s rho方法分解n;

(2)知道a、b的值分解n;

(3)知道g的值分解n;

(4)分解N-1。

baby_rsa |$p, q=v_i^{m_i+1}−(v_i+1)^{m_i}$

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#!/usr/bin/env python3

from Crypto.Util.number import *
from secret import flag, v1, v2, m1, m2


def enc_1(val):
p, q = pow(v1, (m1+1))-pow((v1+1), m1), pow(v2, (m2+1))-pow((v2+1), m2)
assert isPrime(p) and isPrime(q) and (p*q).bit_length() == 2048 and q < p < q << 3
return pow(val, 0x10001, p*q)


def enc_2(val):
assert val.bit_length() < 512
while True:
fac = [getPrime(512) for i in range(3)]
if isPrime(((fac[0]+fac[1]+fac[2]) << 1) - 1):
n = fac[0]*fac[1]*fac[2]*(((fac[0]+fac[1]+fac[2]) << 1) - 1)
break
c = pow(val, 0x10001, n)
return (c, n, ((fac[0]+fac[1]+fac[2]) << 1) - 1)


if __name__ == "__main__":
assert flag[:5] == b'flag{'
plain1 = bytes_to_long(flag[:21])
plain2 = bytes_to_long(flag[21:])
print(enc_1(plain1))
print(enc_2(plain2))

'''
15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
(40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083, 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269, 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739)
'''

题解

en1

条件

p,q的比特长度均小于2048(应该更小)。我们可以通过这个条件来枚举v和m,求出该范围内的所有素数,然后再从中选取任意两个素数,求n,长度若为2048bits,则尝试解密。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import gmpy2
from Crypto.Util.number import *
#enc_1
c1 = 15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311
e1 = 65537

primes = []
for x in range(500):
for y in range(500):
num = pow(x, (y+1))-pow((x+1), y)
if len(bin(num)[2:]) < 2048:
if isPrime(num):
primes.append(num)

for p in primes:
for q in primes:
n1 = p*q
if len(bin(n1)[2:]) == 2048:
try:
d1 = gmpy2.invert(e1,(p-1)*(q-1))
flag = long_to_bytes(pow(c1,d1,n1))
if b'flag' in flag or b'ctf' in flag:
print(flag)
except:
pass
#b'flag{8102c552-3d78-4a'

en2

1
2
3
4
5
6
7
8
9
e2 = 0x10001
c2, n2, p = (40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083, 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269, 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739)
print(gmpy2.is_prime(p))
print(p)
phi2 = (191-1)*(193-1)*(627383-1)*(1720754738477317127758682285465031939891059835873975157555031327070111123628789833299433549669619325160679719355338187877758311485785197492710491-1)
d2 = int(gmpy2.invert(e2, phi2))
m2 = pow(c2, d2, p)
print(long_to_bytes(m2))
# #b'42-b659-0c96ef827f05}'

舍掉合数

值得注意,剩下的居然还是个合数,得拆了求其phi

总结

条件

  • 穷举所有v,m(即穷举所有p、q)

special_rsa | (e|p-1) & (e|q-1)

有限域开e次方,解决问题。

但e不能太大🤔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#脚本2
#Sage
import libnum

c = 53296318153341311013989348488093143123693921875654781175946491674187297
p = 953730950786751671162019537171974567
q = 1189933229053113361422958527792232151
e = 113

P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
f=a^e-c
mps=f.monic().roots()

P.<a>=PolynomialRing(Zmod(q),implementation='NTL')
g=a^e-c
mqs=g.monic().roots()

for mpp in mps:
x=mpp[0]
for mqq in mqs:
y=mqq[0]
solution = CRT_list([int(x), int(y)], [p, q])
print(libnum.n2s(int(solution)))

总结

  • (e|p-1) & (e|q-1), AMM算法解决

CVE OF RSA |p=km+(65537*a % n)

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def special_rsa(self):
kbits = 37
abit = 62
M = 962947420735983927056946215901134429196419130606213075415963491270
while True:
k = getRandomNBitInteger(kbits)
a = getRandomNBitInteger(abit)
p = k * M + pow(0x10001, a, M)
if isPrime(p):
break
while True:
l = getRandomNBitInteger(kbits)
b = getRandomNBitInteger(abit)
q = l * M + pow(0x10001, b, M)
if isPrime(q):
break
n = p * q
self.send(b'n = ' + str(n).encode())
flag = open('flag', 'rb').read()
m = bytes_to_long(flag)
c = pow(m, 0x10001, n)
self.send(b'c = ' + str(c).encode())
self.request.close()

总结

babyrsa |低加密指数广播攻击

题目

1
2
3
4
5
n =  []
c = []
f=lambda m,e,n,c:pow(m,e,n)==c#应该是满足这个条件就为1
assert(sum(map(f,[p]*4,[4]*4,n,c))==4)#也就是说四次加密都是对的,这样总和才能为4
#map(f,m,e,n,c) e = 4 同明文同指数 多次加密 中国剩余定理

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
def CRT(cl, nl):
assert (reduce(gmpy2.gcd, nl) == 1)
assert (isinstance(nl, list) and isinstance(cl, list))
M = reduce(lambda x, y: x * y, nl)
cl_ti_nl = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(nl, cl)]
return reduce(lambda x, y: x + y, cl_ti_nl) % M

n = []
c = []

m_4 = CRT(c, n)
p = int(gmpy2.iroot(m_4, 4)[0])
print(p)

总结

  • $m^e ≡ c \mod(n)$ 由CRT得$m^e$,开e次方即解

Rabin |模4不余3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
from Crypto.Util.number import getPrime
from random import randint
from libnum import *
from gmpy2 import *


def power(s1, s2, k1, k2, w, p):
return ((s1*k1+s2*k2*w)%p, (s1*k2+s2*k1)%p)

def Cipolla_algorithm(p, n):
a = randint(1, p)
w = a ** 2 - n

while pow(w, (p-1)/2, p) !=p-1 :
a = randint(1, p)
w = a ** 2 - n

times = (p+1)/2

k1 = 1
k2 = 0

first = True

sum1 = 1
sum2 = 0
while times != 0:
if first:
k1, k2=power(k1, k2, a, 1, w, p)
first = False

else:
k1, k2=power(k1, k2, k1, k2, w, p)

if times & 1:
sum1, sum2 = power(sum1, sum2, k1, k2, w, p)
times >>= 1

return sum1

def CRT(c, n):
for i in range(len(n)):
for j in range(i + 1, len(n)):
assert gcd(n[i], n[j]) == 1
assert len(c) == len(n)

N = reduce(lambda a, b: a*b, n)
x = 0
for i, j in zip(c, n):
N_i = N/j
N_i_1 = invert(N_i, j)
x+=i*N_i*N_i_1
return x % N

if __name__ == '__main__':
p = getPrime(512)
while p % 4 != 1:
p = getPrime(512)

q = getPrime(512)
while q % 4 != 1:
q = getPrime(512)
n = p * q
m = s2n('this is plaintext')
c = pow(m, 2, n)
print 'm is '+str(m)

get_x1 = Cipolla_algorithm(p, c)
get_x2 = Cipolla_algorithm(q, c)


assert pow(get_x1, 2, p) == c % p
assert pow(get_x2, 2, q) == c % q

c11 = get_x1
c12 = p-get_x1
c21 = get_x2
c22 = q-get_x2

print 'possible m :' + str(CRT([c11, c21], [p, q]))
print 'possible m :' + str(CRT([c11, c22], [p, q]))
print 'possible m :' + str(CRT([c12, c21], [p, q]))
print 'possible m :' + str(CRT([c12, c22], [p, q]))

n次同余方程

1
2
3
4
5
6
7
8
9
10
11
from Crypto.Util.number import getPrime
from random import randint
from sympy.ntheory.residue_ntheory import nthroot_mod

p = getPrime(150)
x = randint(1, p)
n = pow(x, 4, p)

x1 = nthroot_mod(n,4,p,all_roots=False)
assert pow(x1, 4, p) == n
print x1

Swedish RSA |多项式RSA

有限域上的多项式

  • 有限域:有限个数的集合
  • 有限域多项式系数属于某个有限域的多项式
  • 有限域下不可约多项式:一个多项式不能被拆成多个同一有限域下多个多项式的乘积

加解密

  1. 对系数定义在GF(p)上的多项式N

    • 拆解之,得到多项式P、Q

      即:N = P * Q

  2. 计算N的欧拉函数phi

    如何求phi

    • 记在GF(p)上, X的最高次数为a,则:

      $$\phi (X) = p^a - 1$$

    即:$$\phi (N) = \phi (P) * \phi (Q) = (p^{P.degree()}-1)*(p^{Q.degree()}-1)$$

  3. 选一个整数e,(e, phi)=1,并求出逆元d,e×d≡1(mod phi)

  4. 加密:$$C= M^e \mod N$$

  5. 解密:$$M = C^d \mod N$$

    明文转换成多项式

    • 将明文每个字符转ascii,作为多项式m的系数

其中e和d都是整数,它们和多项式可以进行模幂运算

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#!/usr/bin/env sage
# -*- coding: utf-8 -*-
p = 43753

R.<x> = PolynomialRing(GF(p))

N = 34036*x^177 + 23068*x^176 + 13147*x^175 + 36344*x^174 + 10045*x^173 + 41049*x^172 + 17786*x^171 + 16601*x^170 + 7929*x^169 + 37570*x^168 + 990*x^167 + 9622*x^166 + 39273*x^165 + 35284*x^164 + 15632*x^163 + 18850*x^162 + 8800*x^161 + 33148*x^160 + 12147*x^159 + 40487*x^158 + 6407*x^157 + 34111*x^156 + 8446*x^155 + 21908*x^154 + 16812*x^153 + 40624*x^152 + 43506*x^151 + 39116*x^150 + 33011*x^149 + 23914*x^148 + 2210*x^147 + 23196*x^146 + 43359*x^145 + 34455*x^144 + 17684*x^143 + 25262*x^142 + 982*x^141 + 24015*x^140 + 27968*x^139 + 37463*x^138 + 10667*x^137 + 39519*x^136 + 31176*x^135 + 27520*x^134 + 32118*x^133 + 8333*x^132 + 38945*x^131 + 34713*x^130 + 1107*x^129 + 43604*x^128 + 4433*x^127 + 18110*x^126 + 17658*x^125 + 32354*x^124 + 3219*x^123 + 40238*x^122 + 10439*x^121 + 3669*x^120 + 8713*x^119 + 21027*x^118 + 29480*x^117 + 5477*x^116 + 24332*x^115 + 43480*x^114 + 33406*x^113 + 43121*x^112 + 1114*x^111 + 17198*x^110 + 22829*x^109 + 24424*x^108 + 16523*x^107 + 20424*x^106 + 36206*x^105 + 41849*x^104 + 3584*x^103 + 26500*x^102 + 31897*x^101 + 34640*x^100 + 27449*x^99 + 30962*x^98 + 41434*x^97 + 22125*x^96 + 24314*x^95 + 3944*x^94 + 18400*x^93 + 38476*x^92 + 28904*x^91 + 27936*x^90 + 41867*x^89 + 25573*x^88 + 25659*x^87 + 33443*x^86 + 18435*x^85 + 5934*x^84 + 38030*x^83 + 17563*x^82 + 24086*x^81 + 36782*x^80 + 20922*x^79 + 38933*x^78 + 23448*x^77 + 10599*x^76 + 7156*x^75 + 29044*x^74 + 23605*x^73 + 7657*x^72 + 28200*x^71 + 2431*x^70 + 3860*x^69 + 23259*x^68 + 14590*x^67 + 33631*x^66 + 15673*x^65 + 36049*x^64 + 29728*x^63 + 22413*x^62 + 18602*x^61 + 18557*x^60 + 23505*x^59 + 17642*x^58 + 12595*x^57 + 17255*x^56 + 15316*x^55 + 8948*x^54 + 38*x^53 + 40329*x^52 + 9823*x^51 + 5798*x^50 + 6379*x^49 + 8662*x^48 + 34640*x^47 + 38321*x^46 + 18760*x^45 + 13135*x^44 + 15926*x^43 + 34952*x^42 + 28940*x^41 + 13558*x^40 + 42579*x^39 + 38015*x^38 + 33788*x^37 + 12381*x^36 + 195*x^35 + 13709*x^34 + 31500*x^33 + 32994*x^32 + 30486*x^31 + 40414*x^30 + 2578*x^29 + 30525*x^28 + 43067*x^27 + 6195*x^26 + 36288*x^25 + 23236*x^24 + 21493*x^23 + 15808*x^22 + 34500*x^21 + 6390*x^20 + 42994*x^19 + 42151*x^18 + 19248*x^17 + 19291*x^16 + 8124*x^15 + 40161*x^14 + 24726*x^13 + 31874*x^12 + 30272*x^11 + 30761*x^10 + 2296*x^9 + 11017*x^8 + 16559*x^7 + 28949*x^6 + 40499*x^5 + 22377*x^4 + 33628*x^3 + 30598*x^2 + 4386*x + 23814
c = 5209*x^176 + 10881*x^175 + 31096*x^174 + 23354*x^173 + 28337*x^172 + 15982*x^171 + 13515*x^170 + 21641*x^169 + 10254*x^168 + 34588*x^167 + 27434*x^166 + 29552*x^165 + 7105*x^164 + 22604*x^163 + 41253*x^162 + 42675*x^161 + 21153*x^160 + 32838*x^159 + 34391*x^158 + 832*x^157 + 720*x^156 + 22883*x^155 + 19236*x^154 + 33772*x^153 + 5020*x^152 + 17943*x^151 + 26967*x^150 + 30847*x^149 + 10306*x^148 + 33966*x^147 + 43255*x^146 + 20342*x^145 + 4474*x^144 + 3490*x^143 + 38033*x^142 + 11224*x^141 + 30565*x^140 + 31967*x^139 + 32382*x^138 + 9759*x^137 + 1030*x^136 + 32122*x^135 + 42614*x^134 + 14280*x^133 + 16533*x^132 + 32676*x^131 + 43070*x^130 + 36009*x^129 + 28497*x^128 + 2940*x^127 + 9747*x^126 + 22758*x^125 + 16615*x^124 + 14086*x^123 + 13038*x^122 + 39603*x^121 + 36260*x^120 + 32502*x^119 + 17619*x^118 + 17700*x^117 + 15083*x^116 + 11311*x^115 + 36496*x^114 + 1300*x^113 + 13601*x^112 + 43425*x^111 + 10376*x^110 + 11551*x^109 + 13684*x^108 + 14955*x^107 + 6661*x^106 + 12674*x^105 + 21534*x^104 + 32132*x^103 + 34135*x^102 + 43684*x^101 + 837*x^100 + 29311*x^99 + 4849*x^98 + 26632*x^97 + 26662*x^96 + 10159*x^95 + 32657*x^94 + 12149*x^93 + 17858*x^92 + 35805*x^91 + 19391*x^90 + 30884*x^89 + 42039*x^88 + 17292*x^87 + 4694*x^86 + 1497*x^85 + 1744*x^84 + 31071*x^83 + 26246*x^82 + 24402*x^81 + 22068*x^80 + 39263*x^79 + 23703*x^78 + 21484*x^77 + 12241*x^76 + 28821*x^75 + 32886*x^74 + 43075*x^73 + 35741*x^72 + 19936*x^71 + 37219*x^70 + 33411*x^69 + 8301*x^68 + 12949*x^67 + 28611*x^66 + 42654*x^65 + 6910*x^64 + 18523*x^63 + 31144*x^62 + 21398*x^61 + 36298*x^60 + 27158*x^59 + 918*x^58 + 38601*x^57 + 4269*x^56 + 5699*x^55 + 36444*x^54 + 34791*x^53 + 37978*x^52 + 32481*x^51 + 8039*x^50 + 11012*x^49 + 11454*x^48 + 30450*x^47 + 1381*x^46 + 32403*x^45 + 8202*x^44 + 8404*x^43 + 37648*x^42 + 43696*x^41 + 34237*x^40 + 36490*x^39 + 41423*x^38 + 35792*x^37 + 36950*x^36 + 31086*x^35 + 38970*x^34 + 12439*x^33 + 7963*x^32 + 16150*x^31 + 11382*x^30 + 3038*x^29 + 20157*x^28 + 23531*x^27 + 32866*x^26 + 5428*x^25 + 21132*x^24 + 13443*x^23 + 28909*x^22 + 42716*x^21 + 6567*x^20 + 24744*x^19 + 8727*x^18 + 14895*x^17 + 28172*x^16 + 30903*x^15 + 26608*x^14 + 27314*x^13 + 42224*x^12 + 42551*x^11 + 37726*x^10 + 11203*x^9 + 36816*x^8 + 5537*x^7 + 20301*x^6 + 17591*x^5 + 41279*x^4 + 7999*x^3 + 33753*x^2 + 34551*x + 9659
S.<x> = R.quotient(N)
#sage 里 ^ 与 ** 相同
P, Q = N.factor()
P, Q = P[0], Q[0]
print(P.degree(), Q.degree()) # 次数,即:最高次
phi = (p ** P.degree() - 1) * (p ** Q.degree() - 1)
e = 0x10001
d = inverse_mod(e, phi)

m = pow(c, d, N) # 多项式m的各系数为明文每个字符对应的ascii码
m = "".join([chr(c) for c in m.list()])
print(m)

unusualrsa2 |线性关系Franklin-Reiter攻击

一言以蔽之,利用多项式gcd得到最大公因子$x-M$

其中e=3的证明情况见CTF-Wiki,更全面的看上面论文

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from functools import reduce
from secret import flag, x, y

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

assert(reduce(lambda x,y:x&y,[(i-5)*i+6==0 for i in x]))
assert(reduce(lambda x,y:x&y,[(j-15)*j+44==0 for j in y]))

print(pow(reduce(lambda x,y:x*m+y,x),17,n))
print(pow(reduce(lambda x,y:x*m+y,y),17,n))

#23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
#10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
#17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450

解题脚本

image-20220506153047159

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#脚本1
#Sage
import binascii
def attack(c1, c2, n, e):
PR.<x>=PolynomialRing(Zmod(n))
# replace a,b,c,d
g1 = (2*x+3)^e - c1
g2 = (4*x+11)^e - c2

def gcd(g1, g2):
while g2:
g1, g2 = g2, g1 % g2
return g1.monic()
return -gcd(g1, g2)[0]
c1 = 10900151504654409767059699202929100225155892269473271859207513720755903691031362539478242920144073599515746938827937863835169270383721094542639011665235593065932998091574636525973099426040452626893461449084383663453549354608769727777329036059746386523843912382289597182615339786437186169811342356085836838520978047561127661777189045888648773949147220411427306098338616422692914110656004863767719312410906124366000507952960331116878197129010412361636679449281808407214524741732730279777729251515759320442591663641984363061618865267606007355576230009922421807527598213455112981354590909603317525854070358390622096569841
c2 = 17298679220717326374674940612143058330715465693318467692839033642321129433471254547497087746971317567301086124779289015934582615377165560688447452762043163082394944604062014490446763247008217251611443338103074143809936437694543761369945095202092750900940979469994907399829695696313513303922266742415376818434932335640062684245008822643258497589196668426788916969378417960200705779461808292296450298558001909603602502604228973101048082095642290047196235959438278631661658312398313171590515776453711432353011579809351076532129444735206408591345372296372378396539831385036814349328459266432393612919118094115543053115450
n = 23772599983135215481563178266884362291876571759991288577057472733374903836591330410574958472090396886895304944176208711481780781286891334062794555288959410390926474473859289842654809538435377431088422352076225067494924657598298955407771484146155998883073439266427190212827600119365643065276814044272790573450938596830336430371987561905132579730619341196199420897034988685012777895002554746080384319298123154671447844799088258541911028041717897434816921424155687677867019535399434825468160227242441375503664915265223696139025407768146464383537556265875013085702422829200814612395116961538432886116917063119749068212699
e = 17
m1 = attack(c1, c2, n, e)
print(binascii.unhexlify("%x" % int(m1)))

unusuarsa4 |inv(q,p),c,d;没n

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long
from gmpy2 import invert
from secret import flag

m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(invert(q,p))

e = 0x10001
d = invert(e,(p-1)*(q-1))
print(d)

c = pow(m,e,n)
print(c)


q_1 = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

题解

理论推理

  • hint1: $$inv(q, p) · phi \mod p$$
  • hint2:
    • 费马小定理
    • 给定r, k1, k2,若 k2|k1,则:$r \mod k2 = (r \mod k1) \mod k2$

记inv(q, p) = q1, 题目给了q1,那么有如下性质:

$$q1* q ≡ 1 \mod p$$

构造hint1的格式:

$$q1•phi ≡ q1•(p-1)•(q-1) ≡ (p-1)•(q1•q - q1) ≡ (p-1) (1-q1) ≡ (1-q1) \mod p$$

即:

$$q1•phi + q1 -1 = k•p$$

记kp = q1*phi + q1 -1 ,则:p | kp

接下来,聚焦hint2,任选满足$gcd(g, p) = 1$的g, 则:

$$g^{phi} ≡ 1 \mod n$$ —> $$g^{phi} ≡ 1 \mod p$$ —> $$(g^{phi} \mod kp) ≡ 1 \mod p$$

即:

$$p |(g^{phi} \mod kp) - 1$$

解题思路

  1. 知道e、d,则:$e*d -1 = k’ * phi$

    利用此,爆破phi

  2. 用爆破出的phi计算kp

  3. 任选两个素数g1, g2(这样有gcd(g, p) =1)

    计算出x1 = $(g_1^{phi} \mod kp) -1$, x2 = $(g_2^{phi} \mod kp) -1$

    易得:p = gcd(x1, x2)

  4. 由phi、p得q、n

  5. RSA解密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import libnum
import gmpy2

e = 0x10001
q1 = 113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512
d = 27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137
c = 619543409290228183446186073184791934402487500047968659800765382797769750763696880547221266055431306972840980865602729031475343233357485820872268765911041297456664938715949124290204230537793877747551374176167292845717246943780371146830637073310108630812389581197831196039107931968703635129091224513813241403591357678410312272233389708366642638825455844282490676862737715585788829936919637988039113463707959069907015464745700766013573282604376277598510224455044288896809217461295080140187509519005245601483583507547733673523120385089098002298314719617693895392148294399937798485146568296114338393548124451378170302291

k = 1
while True:
if (e * d - 1) % k == 0:
phi = (e * d - 1) // k
kp = q1 * phi - q1 + 1
x1 = pow(3, phi, kp) - 1
x2 = pow(5, phi, kp) - 1
x = gmpy2.gcd(x1, x2)
if len(str(bin(x)).replace('0b', '')) == 1024:
p = x
q = (phi // (p - 1)) + 1
n = p * q
m = pow(c, d, n)
print(m)
print(libnum.n2s(int(m)))
k += 1

unusualrsa1 |m高位泄漏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# ********************
# @Author: Lazzaro
# ********************

from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
from random import randint
from secret import flag

p = getPrime(1024)
q = getPrime(1024)
n = p*q
print(n)

m = bytes_to_long(long_to_bytes(randint(0,30))*208+flag)
assert(m.bit_length()==2044)
print((m>>315)<<315)
c = pow(m,3,n)
print(c)

#14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
#1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
#6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819

题解

m高位泄漏

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# sage
from Crypto.Util.number import *

n = 14113948189208713011909396304970377626324044633561155020366406284451614054260708934598840781397326960921718892801653205159753091559901114082556464576477585198060530094478860626532455065960136263963965819002575418616768412539016154873800614138683106056209070597212668250136909436974469812231498651367459717175769611385545792201291192023843434476550550829737236225181770896867698281325858412643953550465132756142888893550007041167700300621499970661661288422834479368072744930285128061160879720771910458653611076539210357701565156322144818787619821653007453741709031635862923191561438148729294430924288173571196757351837
mbar = 1520800285708753284739523608878585974609134243280728660335545667177630830064371336150456537012842986526527904043383436211487979254140749228004148347597566264500276581990635110200009305900689510908049771218073767918907869112593870878204145615928290375086195098919355531430003571366638390993296583488184959318678321571278510231561645872308920917404996519309473979203661442792048291421574603018835698487725981963573816645574675640357569465990665689618997534740389987351864738104038598104713275375385003471306823348792559733332094774873827383320058176803218213042061965933143968710199376164960850951030741280074168795136
c = 6635663565033382363211849843446648120305449056573116171933923595209656581213410699649926913276685818674688954045817246263487415328838542489103709103428412175252447323358040041217431171817865818374522191881448865227314554997131690963910348820833080760482835650538394814181656599175839964284713498394589419605748581347163389157651739759144560719049281761889094518791244702056048080280278984031050608249265997808217512349309696532160108250480622956599732443714546043439089844571655280770141647694859907985919056009576606333143546094941635324929407538860140272562570973340199814409134962729885962133342668270226853146819
e = 3
kbits = 315

PR.<x>=PolynomialRing(Zmod(n))
f = (mbar + x) ^ e - c
x0 = f.small_roots(X=2^kbits, beta=1)[0] # find root < 2^kbits with factor = n

print(long_to_bytes(int(mbar) + int(x0)))

[长安杯 2021]checkin |威尔逊定理

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
from secret import flag
p = getPrime(1024)
q = getPrime(16)
n = p*q
m = bytes_to_long(flag)
for i in range(1,p-q):
m = m*i%n
e = 1049
print(pow(2,e,n))
print(pow(m,e,n))
#4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
#3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270

题解

前置知识

威尔逊定理:

  • 对于素数p有充分必要条件:

    $$(p-1)! ≡ -1 \mod p$$

聚焦题目,已知:

  1. $$c1 = 2^e \mod n$$
  2. $$c2 = m^{e} \mod n$$
  3. e = 1049

利用 1 ,得到:$c1 - 2^e = k*n$

分解$c1-2^e$再根据位数,得到p、q

解出m_(此m_显然不是flag对应的long型数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import gmpy2
import libnum
c1 = 4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c2 = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
e = 1049
kn = pow(2, e) - c1
# kn = k*p*q
# 分解得p、q:
p = 170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
q = 34211
n = p*q
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m_ = int(pow(c2, d, n)) # m_不是flag对应的m

看题目代码里,唯一复杂的部分:

1
2
for i in range(1,p-q):
m = m*i%n

以下,推理其性质

$$m_0$$(flag对应的)

$$m1 = (m_0 * 1) \mod n$$

$$m2 = (((m_0 * 1)\mod n) *2) \mod n = (m_0 * 1 *2) \mod n$$

$$ m3 = (((m_0 * 1 2)\mod n)3) \mod n = (m_0 * 1 *2 *3) \mod n$$

$$m_n = (m_0 * p!) \mod n$$

实际做题时,就是看到阶乘才知道利用威尔逊定理

由题目,得:

m_ = $$(m_0 * (p-q-1)!) \mod n$$

等号是兼容同余的,由同余性质9有:m_ $≡ (m_0 * (p-q-1)!) \mod p$

则,有:m_ $= (m_0 * (p-q-1)!) \mod p$

为使用威尔逊定理,构造出p!

$(m\_ • [(p-q)•(p-q+1)•…•(p-1)] ) \mod p = m_0•(p-1)! \mod p$

由威尔逊定理,得:$(m\_• [(p-q)•(p-q+1)•…•(p-1)]) \mod p = m_0•(p-1)! \mod p = -m_0 \mod p$

那么,m0 = (inv(-1, p)*m_ * [(p-q)*(p-q+1)*...*(p-1)]) mod p + k*p

这里另一个难题是,求m_ * ([p-q)*(p-q+1)*...*(p-1)]) mod p)

其实,利用题目的给的格式即可求得,然后爆破m0,解出flag

1
2
3
4
5
6
7
8
9
10
11
12
13
for i in range(p-q, p):
m_ = m_ * i % p

m = -m_ % p # 本质上是 inv(-1, p)*m_ % q
k = 0
while True:
print('k=', k)
m += k*p
flag = libnum.n2s(m)
if "flag" in str(flag):
print(flag)
break
k += 1

总代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import gmpy2
import libnum
c1 = 4513855932190587780512692251070948513905472536079140708186519998265613363916408288602023081671609336332823271976169443708346965729874135535872958782973382975364993581165018591335971709648749814573285241290480406050308656233944927823668976933579733318618949138978777831374262042028072274386196484449175052332019377
c2 = 3303523331971096467930886326777599963627226774247658707743111351666869650815726173155008595010291772118253071226982001526457616278548388482820628617705073304972902604395335278436888382882457685710065067829657299760804647364231959804889954665450340608878490911738748836150745677968305248021749608323124958372559270
e = 1049
kn = pow(2, e) - c1
# kn = k*p*q
# 分解得p、q:
p = 170229264879724117919007372149468684565431232721075153274808454126426741324966131188484635914814926870341378228417496808202497615585946352638507704855332363766887139815236730403246238633855524068161116748612090155595549964229654262432946553891601975628848891407847198187453488358420350203927771308228162321231
q = 34211
n = p*q
phi = (p-1)*(q-1)
d = int(gmpy2.invert(e, phi))
m_ = int(pow(c2, d, n)) # m_不是flag对应的m

for i in range(p-q, p):
m_ = m_ * i % p

m = -m_ % p # 本质上是 inv(-1, p)*m_ % q
print(libnum.n2s(m))

boneh_durfee |e大d小

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import bytes_to_long, long_to_bytes, getPrime
from gmpy2 import invert

flag = b"novaCTF{******}"
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
d = getPrime(260)
phi = (p-1)*(q-1)
e = invert(d, phi)
c = pow(m, e, n)
print(e)
print(n)
print(c)
# e= 28366532045084591636437544767374939012961757129620507106907154467035496029282857415182567552270978206397793889819857945701555381457862312304572366567535998525153574576210520634959025982966194022680398054500011866734299857844098161391787585786609289654556120958843118695788794035767689727287572845453232286487
# n =
# c =

题解

  • e非常非常大,我的本能是Wiener attack.

    实际跑起来,说无解,看来不适用。

  • n也拆不出来

  • 搜索题目boneh_durfee,找到F2X师傅师傅给的脚本,跑出了私钥d

    d = 1604729467840738070847003596064117868379286998792964612314423127886316878631207

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    258
    259
    260
    261
    262
    263
    264
    265
    266
    267
    268
    269
    270
    271
    272
    273
    274
    275
    276
    277
    278
    279
    280
    281
    282
    283
    284
    285
    286
    287
    288
    289
    290
    291
    292
    293
    294
    295
    296
    297
    298
    299
    300
    301
    302
    303
    304
    305
    306
    307
    308
    309
    310
    311
    312
    313
    314
    315
    316
    317
    318
    319
    320
    321
    322
    323
    324
    325
    326
    327
    328
    329
    330
    331
    332
    333
    334
    335
    import time

    """
    Setting debug to true will display more informations
    about the lattice, the bounds, the vectors...
    """
    debug = True

    """
    Setting strict to true will stop the algorithm (and
    return (-1, -1)) if we don't have a correct
    upperbound on the determinant. Note that this
    doesn't necesseraly mean that no solutions
    will be found since the theoretical upperbound is
    usualy far away from actual results. That is why
    you should probably use `strict = False`
    """
    strict = False

    """
    This is experimental, but has provided remarkable results
    so far. It tries to reduce the lattice as much as it can
    while keeping its efficiency. I see no reason not to use
    this option, but if things don't work, you should try
    disabling it
    """
    helpful_only = True
    dimension_min = 7 # stop removing if lattice reaches that dimension

    ############################################
    # Functions
    ##########################################

    # display stats on helpful vectors
    def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
    if BB[ii,ii] >= modulus:
    nothelpful += 1

    print (nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")

    # display matrix picture with 0 and X
    def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
    a = ('%02d ' % ii)
    for jj in range(BB.dimensions()[1]):
    a += '0' if BB[ii,jj] == 0 else 'X'
    if BB.dimensions()[0] < 60:
    a += ' '
    if BB[ii, ii] >= bound:
    a += '~'
    print (a)

    # tries to remove unhelpful vectors
    # we start at current = n-1 (last vector)
    def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0] <= dimension_min:
    return BB

    # we start by checking from the end
    for ii in range(current, -1, -1):
    # if it is unhelpful:
    if BB[ii, ii] >= bound:
    affected_vectors = 0
    affected_vector_index = 0
    # let's check if it affects other vectors
    for jj in range(ii + 1, BB.dimensions()[0]):
    # if another vector is affected:
    # we increase the count
    if BB[jj, ii] != 0:
    affected_vectors += 1
    affected_vector_index = jj

    # level:0
    # if no other vectors end up affected
    # we remove it
    if affected_vectors == 0:
    print ("* removing unhelpful vector", ii)
    BB = BB.delete_columns([ii])
    BB = BB.delete_rows([ii])
    monomials.pop(ii)
    BB = remove_unhelpful(BB, monomials, bound, ii-1)
    return BB

    # level:1
    # if just one was affected we check
    # if it is affecting someone else
    elif affected_vectors == 1:
    affected_deeper = True
    for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
    # if it is affecting even one vector
    # we give up on this one
    if BB[kk, affected_vector_index] != 0:
    affected_deeper = False
    # remove both it if no other vector was affected and
    # this helpful vector is not helpful enough
    # compared to our unhelpful one
    if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
    print ("* removing unhelpful vectors", ii, "and", affected_vector_index)
    BB = BB.delete_columns([affected_vector_index, ii])
    BB = BB.delete_rows([affected_vector_index, ii])
    monomials.pop(affected_vector_index)
    monomials.pop(ii)
    BB = remove_unhelpful(BB, monomials, bound, ii-1)
    return BB
    # nothing happened
    return BB

    """
    Returns:
    * 0,0 if it fails
    * -1,-1 if `strict=true`, and determinant doesn't bound
    * x0,y0 the solutions of `pol`
    """
    def boneh_durfee(pol, modulus, mm, tt, XX, YY):
    """
    Boneh and Durfee revisited by Herrmann and May

    finds a solution if:
    * d < N^delta
    * |x| < e^delta
    * |y| < e^0.5
    whenever delta < 1 - sqrt(2)/2 ~ 0.292
    """

    # substitution (Herrman and May)
    PR.<u, x, y> = PolynomialRing(ZZ)
    Q = PR.quotient(x*y + 1 - u) # u = xy + 1
    polZ = Q(pol).lift()

    UU = XX*YY + 1

    # x-shifts
    gg = []
    for kk in range(mm + 1):
    for ii in range(mm - kk + 1):
    xshift = x^ii * modulus^(mm - kk) * polZ(u, x, y)^kk
    gg.append(xshift)
    gg.sort()

    # x-shifts list of monomials
    monomials = []
    for polynomial in gg:
    for monomial in polynomial.monomials():
    if monomial not in monomials:
    monomials.append(monomial)
    monomials.sort()

    # y-shifts (selected by Herrman and May)
    for jj in range(1, tt + 1):
    for kk in range(floor(mm/tt) * jj, mm + 1):
    yshift = y^jj * polZ(u, x, y)^kk * modulus^(mm - kk)
    yshift = Q(yshift).lift()
    gg.append(yshift) # substitution

    # y-shifts list of monomials
    for jj in range(1, tt + 1):
    for kk in range(floor(mm/tt) * jj, mm + 1):
    monomials.append(u^kk * y^jj)

    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
    BB[ii, 0] = gg[ii](0, 0, 0)
    for jj in range(1, ii + 1):
    if monomials[jj] in gg[ii].monomials():
    BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](UU,XX,YY)

    # Prototype to reduce the lattice
    if helpful_only:
    # automatically remove
    BB = remove_unhelpful(BB, monomials, modulus^mm, nn-1)
    # reset dimension
    nn = BB.dimensions()[0]
    if nn == 0:
    print ("failure")
    return 0,0

    # check if vectors are helpful
    if debug:
    helpful_vectors(BB, modulus^mm)

    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(mm*nn)
    if det >= bound:
    print ("We do not have det < bound. Solutions might not be found.")
    print ("Try with highers m and t.")
    if debug:
    diff = (log(det) - log(bound)) / log(2)
    print ("size det(L) - size e^(m*n) = ", floor(diff))
    if strict:
    return -1, -1
    else:
    print ("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")

    # display the lattice basis
    if debug:
    matrix_overview(BB, modulus^mm)

    # LLL
    if debug:
    print ("optimizing basis of the lattice via LLL, this can take a long time")

    BB = BB.LLL()

    if debug:
    print ("LLL is done!")

    # transform vector i & j -> polynomials 1 & 2
    if debug:
    print ("looking for independent vectors in the lattice")
    found_polynomials = False

    for pol1_idx in range(nn - 1):
    for pol2_idx in range(pol1_idx + 1, nn):
    # for i and j, create the two polynomials
    PR.<w,z> = PolynomialRing(ZZ)
    pol1 = pol2 = 0
    for jj in range(nn):
    pol1 += monomials[jj](w*z+1,w,z) * BB[pol1_idx, jj] / monomials[jj](UU,XX,YY)
    pol2 += monomials[jj](w*z+1,w,z) * BB[pol2_idx, jj] / monomials[jj](UU,XX,YY)

    # resultant
    PR.<q> = PolynomialRing(ZZ)
    rr = pol1.resultant(pol2)

    # are these good polynomials?
    if rr.is_zero() or rr.monomials() == [1]:
    continue
    else:
    print ("found them, using vectors", pol1_idx, "and", pol2_idx)
    found_polynomials = True
    break
    if found_polynomials:
    break

    if not found_polynomials:
    print ("no independant vectors could be found. This should very rarely happen...")
    return 0, 0

    rr = rr(q, q)

    # solutions
    soly = rr.roots()

    if len(soly) == 0:
    print ("Your prediction (delta) is too small")
    return 0, 0

    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]

    #
    return solx, soly

    def example():
    ############################################
    # How To Use This Script
    ##########################################

    #
    # The problem to solve (edit the following values)
    #

    # the modulus
    N = 116619053095181844867756588238123176803022888638090603550604610234584486986893904698844566541567093613495764007369858037838298617868152946508912345019503344911355228396374219771717648337137214599383155473846763062399405332170035904047911459812639096963243997609662442560069465026848168759806881590989694374289
    # the public exponent
    e = 28366532045084591636437544767374939012961757129620507106907154467035496029282857415182567552270978206397793889819857945701555381457862312304572366567535998525153574576210520634959025982966194022680398054500011866734299857844098161391787585786609289654556120958843118695788794035767689727287572845453232286487

    # the hypothesis on the private exponent (the theoretical maximum is 0.292)
    delta = 0.280 # this means that d < N^delta

    #
    # Lattice (tweak those values)
    #

    # you should tweak this (after a first run), (e.g. increment it until a solution is found)
    m = 4 # size of the lattice (bigger the better/slower)

    # you need to be a lattice master to tweak these
    t = int((1-2*delta) * m) # optimization from Herrmann and May
    X = 2*floor(N^delta) # this _might_ be too much
    Y = floor(N^(1/2)) # correct if p, q are ~ same size

    #
    # Don't touch anything below
    #

    # Problem put in equation
    P.<x,y> = PolynomialRing(ZZ)
    A = int((N+1)/2)
    pol = 1 + x * (A + y)

    #
    # Find the solutions!
    #

    # Checking bounds
    if debug:
    print ("=== checking values ===")
    print ("* delta:", delta)
    print ("* delta < 0.292", delta < 0.292)
    print ("* size of e:", int(log(e)/log(2)))
    print ("* size of N:", int(log(N)/log(2)))
    print ("* m:", m, ", t:", t)

    # boneh_durfee
    if debug:
    print ("=== running algorithm ===")
    start_time = time.time()

    solx, soly = boneh_durfee(pol, e, m, t, X, Y)

    # found a solution?
    if solx > 0:
    print ("=== solution found ===")
    if False:
    print ("x:", solx)
    print ("y:", soly)

    d = int(pol(solx, soly) / e)
    print ("private key found:", d)
    else:
    print ("=== no solution was found ===")

    if debug:
    print("=== %s seconds ===" % (time.time() - start_time))

    if __name__ == "__main__":
    example()
  • rsa解密,得到flag

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import libnum

    d = 1604729467840738070847003596064117868379286998792964612314423127886316878631207
    e= 28366532045084591636437544767374939012961757129620507106907154467035496029282857415182567552270978206397793889819857945701555381457862312304572366567535998525153574576210520634959025982966194022680398054500011866734299857844098161391787585786609289654556120958843118695788794035767689727287572845453232286487
    n = 116619053095181844867756588238123176803022888638090603550604610234584486986893904698844566541567093613495764007369858037838298617868152946508912345019503344911355228396374219771717648337137214599383155473846763062399405332170035904047911459812639096963243997609662442560069465026848168759806881590989694374289
    c = 5550387375810892705924800464945980988431639193797468627845836397962361427321133854633770242318969576163563079147919098794998899335191281861385800469677049957403290859349688725585260874592933564793273307183923684839207469443101629472424936878786558261355723914033881683475668259544365455286750343306090149047
    m = int(pow(c, d, n))
    print(libnum.n2s(m))
    # b"novaCTF{d0n't_J0_kn0wn_b0n3h_durf33}"

总结

e过大求解再添一员猛将

e 非常大接近于N,即 d 较小时。与低解密指数攻击类似,比低解密指数攻击(Wiener Attack)更强,可以解决$\frac{1}{3} N^{\frac{1}{4}} ≤ d ≤ N^{0.292}$的问题。

  • 若 $d < \frac{1}{3} N^{\frac{1}{4}}$ ,则可选择Winner攻击
  • 若$\frac{1}{3} N^{\frac{1}{4}} ≤ d ≤ N^{0.292}$,则可选择Boneh和Durffe攻击攻击

Pohlig-hellman |离散对数

1
2
3
4
5
6
7
8
9
10
11
12
13
from Crypto.Util.number import *
import random

flag = b"novaCTF{******}"
n = 2 ** 1024
e = bytes_to_long(flag)
m = 0b101010101010101010100101001010101010010101001010111
c = pow(m, e, n)
print(m)
print(c)

# m = 1501199137581655
# c = 66833442412465837593411329882154519317338634354813852217147677313497719741502965349598626224700154836780839167770562034307746877775924269074354587364763439201631983852896392052544055458196432140978886498016995260963282787641046569867110159856825184627818917769177045102578369482845631041962774517107346776951

题解

  • 昨天晚上集中学习了la佬的sage指南文章,恰好有离散对数问题(Pohlig-hellman)
  • 唯一让我疑惑的是,la佬将n是合数、n是素数或素数的整数幂分为两类,其中n是素数里交代了Pohlig-hellman,但题目里n明显是后者🤔

虽然但是,sage一两行搞定

1
2
3
4
5
6
7
8
9
10
# sage
# m^e = c (mod n)

import libnum
n = 2^1024
m = 1501199137581655
c = 66833442412465837593411329882154519317338634354813852217147677313497719741502965349598626224700154836780839167770562034307746877775924269074354587364763439201631983852896392052544055458196432140978886498016995260963282787641046569867110159856825184627818917769177045102578369482845631041962774517107346776951
e = discrete_log(mod(c,n),mod(m,n))
print(libnum.n2s(int(e)))
# b'novaCTF{th1s_1s_h0w_D1scr3t3_l0g_w0rk}'

总结

  • 离散对数的问题。

    • 当模为素数时,一般用的是大步小步算法(BSGS)
    • 当模为素数的幂时,主要用Pohlig-Hellman

    而sage里的discrete_log就是利用以上两种算法实现的???

    不确定有没有用Pohlig-Hellman算法,因为la佬说它要求底数是原根

想简单一点 |m=c

题目

1
2
3
N = 24873777989291448485268365702265085243886872900039809831478881276969311714448924581398692832639705916538111455861057354225427758736198452679468399039512440497290615485190994957684665065261280544484301856860844163436499302230085760545686486398949018187416289923500558688885485672960734334858119391323987554701544773420070317895909846297195832399677291338220818181502181317849952785959097285626009703863257450199781708945715701136683994546852422993684382468187651935055302074609980311161155531603473091857526099148935429447319415714778860215376802270686310782735079899235228731429165106477537031235405221734008734614847
e = 12436888994645724242634182851132542621943436450019904915739440638484655857224462290699346416319852958269055727930528677112713879368099226339734199519756220248645307742595497478842332532630640272242150928430422081718249651115042880272843243199474509093708144961750279344442742836480367167429059695661993777350613653317802356713323129593521588320771616955563426747034967432053960828426250168954828986666929922730060781213890566121107119389060806644531516491192343284701151238691996162679338542186167193568672632227858449997036747029810933106336313085633759799229646747282205612102678724267585967720538082620536177904609
c = 7539424334663709603622451394173266049480031393220309445902319310504736287365860451132752036622339554159799611768328686792828750952551268647863160547774237934958072391797341405165512721597085695555356929495861914056799039140107261439671707574841789330531198534325422015873621769489969596614802282764401661006564546159674397356683650318142728009273827997179696988926599672213482848150751054351595386402597000601684644207559735499031666361222038615475154046453649719203304187309556004660926226182353445661702352380654352874617084419834338343925880593023307238768452509962

hint: 当你凝视密文的时候,密文也在凝视你

题解

糟了,菜🐔看着题目瑟瑟发抖🤔

c甚至没有e大, 想了很久没想到

最后看4XWi11师傅题解,直接把c转byte得解(半瞬间有过这个想法)

1
WINNER WINNER CHICKEN DINNER! This is easy but quite troll man. One should NOT expect that the ciphertext is equal to plaintext in the real world. Flag is: ctfshow{xielunyan___KAI!}. By the way, what a stupid encryption exponent it is!

m = c

离谱,当个脑洞吧。

站在出题者角度来看是极好的,对于解题者看来一般。

致敬我费的时间😭

ctfshow·单身杯·TooYoungRSA|选择明文攻击

题目

chall.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from nevergonnagiveyouup import n, e
import secrets
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

if __name__ == "__main__":
with open("flag.txt", "rb") as f:
flag = f.read().strip()

k = secrets.randbelow(n)
print(f"ck = {pow(k, e, n)}")
key = sha256(str(k).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
print(f"ct = {cipher.encrypt(pad(flag, AES.block_size)).hex()}")

while True:
nevergonnaletyoudown = int(input("I just wanna tell you how i'm feeling... "))
assert nevergonnaletyoudown >= 0
print(f"gotta make you understand: {pow(nevergonnaletyoudown, e, n)}")

题解

学习参考la佬博客

显而易见,求出k即解

而求k,则需要n、e

我们可以随意传m,并且得到他的密文,典型的选择明文攻击

实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
# SageMath
# 要是能用py实现factor,也可以用python3
import socket
import binascii
import gmpy2
from hashlib import sha256
# import secrets # woc,真的有这个库,求出n后千万别犯傻,以为k = secrets.randbelow(n)
from Crypto.Cipher import AES

HOST = 'pwn.challenge.ctf.show' # str
PORT = ... # int

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((HOST, PORT))
a = str(s.recv(1024))
a = a.split(r'\n')
ck = int(a[0][7:])
ct = binascii.unhexlify(a[1][5:])

print(f'ck = {ck}')
print(f'ct = {ct}')


# 选择明文攻击获得n
def server_encode(data): # 具体代码根据题目修改
s.send((str(data) + '\n').encode())
tmp = str(s.recv(1024))
tmp = int(''.join(tmp.split(': ')[1]).split(r'\n')[0])
print(tmp)
return tmp


def get_n():
nset = []
c2 = server_encode(2)
c4 = server_encode(4)
c8 = server_encode(8)
nset.append(c2 * c2 - c4)
nset.append(c2 * c2 * c2 - c8)
c3 = server_encode(3)
c9 = server_encode(9)
c27 = server_encode(27)
nset.append(c3 * c3 - c9)
nset.append(c3 * c3 * c3 - c27)
c5 = server_encode(5)
c25 = server_encode(25)
c125 = server_encode(125)
nset.append(c5 * c5 - c25)
nset.append(c5 * c5 * c5 - c125)
n = nset[0]
for x in nset:
n = gmpy2.gcd(x, n)
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
print('n =', n)
return n

n = get_n()
p, q = factor(n)
p = int(p[0])
q = int(q[0])
phi = (p-1)*(q-1)

# 用e=65537解密是乱码,遂爆破e
e = 1
m = ''
while 1:
try:
d = int(gmpy2.invert(e, phi))
except:
e += 1
continue
k = int(pow(ck, d, n))
key = sha256(str(k).encode()).digest()
cipher = AES.new(key, AES.MODE_ECB)
m = str(cipher.decrypt(ct))
if 'ctfshow' in m:
print(f'e = {e}')
print(m)
break
e += 1
"""
ck=148323602760763885089965103552365001726
ct=b'K\x19T\x9a\x93/D\xa5\xa4\x0e\xece\\9i\x88j{g\xeaL\xe4\xf6S\xad\x1a\xda\xdd\xcb\xc5\xe0\x08\x8a_uL\x1bA\xef\x0e\x15z\xe0\xe8?\x0f2]'
41666058103470588962345640003523069436
87974072322452812802060456816244684047
179180224211126181096539041274987715617
162876920694220832796871083784876452522
63761152929694183722546668522439686878
127108093007738641972094354046766635400
26538414660849576349306084798330618579
11192818723856101924902980552900607917
11687269834469407485578275151617352981
n = 184885676198683491485339386905042942577
e=948707
b'ctfshow{...................}\x03\x03\x03'
"""

总结

适用于不知n、e,可以自己发m且得到c的情况

原理分析

  1. 首先发2,即:m = 2,则可得到

    $c_2 = 2^e \mod n$

  2. 其次,我们再发送$2^2$,即:m=4, 则可得到:

    $c4= 4^e \mod n$

    为探究好两者之间的关系,不妨设$2^e = a+bn$, 则有:

    $c_2=2^e \mod n = a+bn \mod n = a$

    $c_4=4^e \mod n = (2^2)^e = (2^e)^2 = (a+bn)^2 = a^2+2abn+b^2n^2 = a^2 \mod n $

    也即:$c_4 = a^2 + kn$, 而此时,我们构造下c2, 即:

    $(c_2)^2 \mod n = a^2 \mod n $, 则: $(c2)^2 = a^2+k’n$

    此时,记$A = (c2)^2 - c4=(k-k’)n = k’’n$

    得到上一步后,我们再接着往下发送🙂

  3. 再则,我们发送$2^3$,即:m=8,同理,则可以得到:

    $B = (c2)^3-c_8=k’’’n$

    好起来了!

    我们用$gcd(A, B)$即得到n,而保险起见,不妨多来几个($2^4、2^5···$)一起求最大公因子

  4. 防污染
    为了防止k值污染到了n(即防止gcd得到的是 一些小数 * n),我们对得到的n简单清洗一下

    (这里前提是n由两大素数p、q相乘)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 自己按照题目要求编写server_encode() 函数
# 实现传入数字后,return int(对应c)
import gmpy2

def get_n():
nset = []
c2 = server_encode(2)
c4 = server_encode(4)
c8 = server_encode(8)
nset.append(c2 * c2 - c4)
nset.append(c2 * c2 * c2 - c8)
c3 = server_encode(3)
c9 = server_encode(9)
c27 = server_encode(27)
nset.append(c3 * c3 - c9)
nset.append(c3 * c3 * c3 - c27)
c5 = server_encode(5)
c25 = server_encode(25)
c125 = server_encode(125)
nset.append(c5 * c5 - c25)
nset.append(c5 * c5 * c5 - c125)
n = nset[0]
for x in nset:
n = gmpy2.gcd(x, n)
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
print('n =', n)
return n

同态加密

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import getPrime as getprime ,long_to_bytes,bytes_to_long,inverse
from vanish import flag
from sympy import isprime,nextprime
import random

m=bytes_to_long(flag)
p=getprime(512) # 酱紫写??
q=nextprime(512)
n=p*q

r=random.randint(1,n)
g=random.randint(1,n)

c=(pow(g,m,n*n)*pow(r,n,n*n))%(n*n)

print "c=%d"%(c)
print "n=%d"%(n)
print "g=%d"%(g)

'''
c=14643617840485727260687883789514337554960495078025159182484344940901600090810578182116617501128323641882943106663241094886209190199404002314247096613925999812837877843566116787148411743428714726661042213165729562285577768043368385746666607442372252641495230532588344276427261824205414379772728577442269620217619275
n=5650215343715484415924649393302012617620686312875699289646188186788806118580423414401283971780836312947326343790326120926819026727018136169739576760024802083
g=786539430846729749998127835613552594423101498023741082894370020014675937062722533682541592019332908209917194089077366019472368764411032602494945304850258108

'''

$c = (g^m \mod n^2)*(r^n \mod n^2)\mod n^2 = g^m * r^n \mod n^2$

给c、n、g

Paillier密码,于1999年由Pascal Paillier发明,是一种用于公钥加密的概率非对称算法。该算法具有加法同态的性质 ; 这意味着,仅给出公钥和m1、m2加密,可以计算出m1 + m2

模式1

  1. 大素数p、q满足$gcd(pq, (p-1)*(q-1)) = 1$
  2. $n=p\cdot q,λ = lcm(p-1, q-1) = \frac{(p-1)\cdot (q-1) }{ gcd(p-1,q-1)}$
  3. 选g, $0<g<n^2$
  4. $L(x) = \frac{x-1}{n}$
  5. $μ = (L(g^λ \pmod {n^2} ))^{-1} \pmod n$
  6. 公钥:(n, g)
  7. 私钥:(λ,μ)

模式2

在模式1的基础上,改写g,λ,μ

  1. $g=n+1$
  2. $λ = φ(n) = (p-1)\cdot (q-1)$
  3. $μ = φ(n)^{-1} \pmod n$

加密

  1. 明文m需要满足$0≤m<n$

  2. 选择随机 r,且满足$gcd(r,n)=1$

  3. 密文:$c=g^m⋅r^n(\mod n^2)$

解密

$m = ( L( c^λ \pmod {n^2} ) \cdot μ ) \pmod n$

题解

分解n,得到p、q

然后跟着解密步骤解就完事了

🤔但p的bit数好像根题目不符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import gmpy2
import libnum


def L(x):
return (x - 1) // n


c = 14643617840485727260687883789514337554960495078025159182484344940901600090810578182116617501128323641882943106663241094886209190199404002314247096613925999812837877843566116787148411743428714726661042213165729562285577768043368385746666607442372252641495230532588344276427261824205414379772728577442269620217619275
n = 5650215343715484415924649393302012617620686312875699289646188186788806118580423414401283971780836312947326343790326120926819026727018136169739576760024802083
g = 786539430846729749998127835613552594423101498023741082894370020014675937062722533682541592019332908209917194089077366019472368764411032602494945304850258108
# print(factor(n))
p = 521
q = 10844943078148722487379365438199640340922622481527253914867923583087919613398125555472713957352852807960319277908495433640727498516349589577235272092178123
la = ((p - 1) * (q - 1)) // int(gmpy2.gcd(p - 1, q - 1))
tmp = L(int(pow(g, la, n ** 2)))
miu = int(gmpy2.invert(tmp, n))
m = (L(int(pow(c, la, n ** 2)) * miu)) % n
print(libnum.n2s(int(m)))

总结

同态加密基于rsa的大素数分解难题,能得到p、q又有公钥就可解