RSA题型总结

Crypto_easy_crypto ｜ N中有大合数

• https://blog.cryptohack.org/cryptoctf2020
• N分解出合数

题目

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

题解

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

题目

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)

题解

###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 很大

• https://blog.csdn.net/qq_52193383/article/details/120642406?spm=1001.2014.3001.5502

题目

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已知

题解

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有公因子

题目

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

题解

# 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}$

• https://blog.csdn.net/qq_52193383/article/details/120392517?spm=1001.2014.3001.5502

题目

#!/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，则尝试解密。

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

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不能太大🤔

• https://blog.csdn.net/LaniakeaHarry/article/details/124384460?spm=1001.2014.3001.5502

#脚本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)

题目

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()

总结

• roca（The Return of Coppersmith’s Attack）攻击
  • 

babyrsa |低加密指数广播攻击

题目

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 同明文同指数 多次加密 中国剩余定理

题解

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

• https://xz.aliyun.com/t/5113

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次同余方程

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

• 参考博客
• https://xz.aliyun.com/t/4545
• https://4xwi11.github.io/posts/80806ae5/?highlight=多项式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都是整数，它们和多项式可以进行模幂运算

题解

#!/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攻击

• 引入

• 《A New Related Message Attack on RSA》

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

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

题目

# ********************
# @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

解题脚本

#脚本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

• 参考博客(4xwill师傅yyds

题目

# ********************
# @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解密

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高位泄漏

# ********************
# @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高位泄漏

# 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 ｜威尔逊定理

题目

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型数字

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(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

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

总代码

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小

题目

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

  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

  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 ｜离散对数

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一两行搞定

# 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

题目

N = 24873777989291448485268365702265085243886872900039809831478881276969311714448924581398692832639705916538111455861057354225427758736198452679468399039512440497290615485190994957684665065261280544484301856860844163436499302230085760545686486398949018187416289923500558688885485672960734334858119391323987554701544773420070317895909846297195832399677291338220818181502181317849952785959097285626009703863257450199781708945715701136683994546852422993684382468187651935055302074609980311161155531603473091857526099148935429447319415714778860215376802270686310782735079899235228731429165106477537031235405221734008734614847
e = 12436888994645724242634182851132542621943436450019904915739440638484655857224462290699346416319852958269055727930528677112713879368099226339734199519756220248645307742595497478842332532630640272242150928430422081718249651115042880272843243199474509093708144961750279344442742836480367167429059695661993777350613653317802356713323129593521588320771616955563426747034967432053960828426250168954828986666929922730060781213890566121107119389060806644531516491192343284701151238691996162679338542186167193568672632227858449997036747029810933106336313085633759799229646747282205612102678724267585967720538082620536177904609
c = 7539424334663709603622451394173266049480031393220309445902319310504736287365860451132752036622339554159799611768328686792828750952551268647863160547774237934958072391797341405165512721597085695555356929495861914056799039140107261439671707574841789330531198534325422015873621769489969596614802282764401661006564546159674397356683650318142728009273827997179696988926599672213482848150751054351595386402597000601684644207559735499031666361222038615475154046453649719203304187309556004660926226182353445661702352380654352874617084419834338343925880593023307238768452509962

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

题解

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

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

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

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

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，并且得到他的密文，典型的选择明文攻击

实现如下

# 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相乘）

代码

# 自己按照题目要求编写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

同态加密

• 参考

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数好像根题目不符

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又有公钥就可解