密码学

Sherry 发布于 2025-05-10 83 次阅读 文章 最后更新于 2025-05-10 3367 字

密码学

本地随机生成对称加密的密钥A
然后用RSA算法加密A,得到密文B
密文B提交给服务器，服务器用私钥解密，得到明文A
后续通信过程，使用明文A来加密

对称加密算法

代表有AES

加密和解密使用相同的密钥

特点

加密速度快，可以加密大量数据

非对称加密算法

代表有RSA

加密和解密使用不同密钥

特点

存在密钥对，公钥 私钥

从公钥无法推导私钥

加密速度慢，加密数据有限

libnum库

import libnum

#字符串转十进制
s="flag{123}"
print(libnum.s2n(s))

#十进制转字符串
j=1889377532526015427453
print(libnum.n2s(j))

#十六进制转字符串
n=0x666c61677b3132337d
print(libnum.n2s(n))

#字符串转十六进制
print(hex(libnum.s2n("flag{123}")))

#二进制转字符串
b='01100001011000110110001001100100'
print(libnum.b2s(b))

#字符串转二进制
s = 'acbd'
print(libnum.s2b(s))

#数字转二进制串
# n=0xfff
# print(s2b(n2s(n)))

#因数分解:返回n的所有素因子及每个素因子的个数。
print(libnum.factorize(1024))

#任意进制转为十进制
print(int('01111',2))
print(int('0x64',16))

gmpy2库

import gmpy2  

# 求模幂  powmod=pow
print gmpy2.powmod(2, 3, 5)  
print gmpy2.powmod(2, 4, 5)  
print gmpy2.powmod(2, 5, 5)  
print  

# 求逆元（常用于RSA）  
p = 3  
q = 7  
e = 7  
n = p * q  
d = gmpy2.invert(e, (p - 1) * (q - 1))  
print d  

# 判断素数  
print gmpy2.is_prime(3)  
print gmpy2.is_prime(6)  
print  

# 欧几里德算法，判断互素  
print gmpy2.gcd(2, 3)  
print gmpy2.gcd(4, 6)  
print  

# 扩展欧几里德算法  
print gmpy2.gcdext(2, 3)  
print gmpy2.gcdext(4, 6)  
print  

# 开n次方根  
print gmpy2.iroot(4, 2)  
print gmpy2.iroot(28, 3)

hashlib库

#md5加密
import hashlib

x = hashlib.md5()
x.update('I_love_python'.encode('utf-8'))
print("x1 = ", x.hexdigest())

# 如果数据量很大，可以分块多次调用 update()，最后计算的结果是一样的
x = hashlib.md5()
x.update('I_love_'.encode('utf-8'))
x.update('python'.encode('utf-8'))
print("x2 = ", x.hexdigest())

#sha1
x = hashlib.sha1()
x.update('I_love_python'.encode('utf-8'))
print("x1 = ", x.hexdigest())

#sha256
x = hashlib.sha256()
x.update('I_love_python'.encode('utf-8'))
print("x1 = ", x.hexdigest())

#sha512
x = hashlib.sha512()
x.update('I_love_python'.encode('utf-8'))
print("x1 = ", x.hexdigest())

Crypto.Util.number库

from Crypto.Util.number import *long_to_bytes,bytes_to_long
flag = b"flag{convert}"
#字节转十进制
nums = bytes_to_long(flag)
#十进制转字节
flag = long_to_bytes(enc)

binascii库

#十六进制的不同表示方式转换
import binascii
a = b'\x01\x02\x03\x04\x05:abcdefghijklmn'
form1 = binascii.hexlify(a)
form2 = binascii.unhexlify(form1)
form3 = binascii.hexlify(a," ") # 第二个形参是定义每个字节之间的间隔符，默认是""

RSA

原理

![[Pasted image 20240609144059.png]]
![[Pasted image 20240609144257.png]]
![[Pasted image 20240609144308.png]]

明文：m=pow(c,d,n)
密文：c=pow(m,e,n)

已知条件：

  • C = m^e mod n
  • m = c^d mod n
  • phi=(p-1) * (q-1)
  • d * e≡1 mod phi
  • dp = d mod (p-1)
  • gcd(e,phi_n)=1

逆元d求解（私钥）

import libnum
import gmpy2

e=65537
phi_n=(p-1)* (q-1)  #欧拉函数
d=gmpy2.invert(e,phi_n)
d=libnum.invmod(e,phi_n）

一般情况下求出d的时候就结束了

基于N分解的RSA题目

[!tip]

N在有一般情况下不可分解的，如果p和q太接近，或相差过大，或q很小等情况

1.在线查询分解网站
http://www.factordb.com/index.php

2.使用yafu工具分解
下载地址：https://sourceforge.net/projects/yafu/

#以分解49为例
yafu-x64.exe factor(49)
#导入文件进行分解，主要注意文本结完要换行！！！不然要报错(由于在命令行里不支持过长的位数，所以我们只要把n的值从文件中去读取即可。  新建一个文件test.txt，内容里写上n的值，如：)
yafu-x64 "factor(@)" -batchfile test.txt

3.使用费马脚本分解

p和q太接近

# _*_ coding:utf-8 _*_
import math

def fermat(n):
    a = math.ceil(math.sqrt(n))
    # b的平方
    b2 = a * a - n
    b = round(math.sqrt(b2))
    while b * b != b2:
        a += 1
        b2 = a * a - n
        b = round(math.sqrt(b2))
    print(a, b, n)
    return a - b, a + b

def factorization(n):
    factors = []
    stack = [n]
    while len(stack) > 0:
        x = stack.pop()
        if x == 2:
            factors.insert(0, x)
            continue
        p, q = fermat(x) if x & 1 == 1 else (2, x // 2)
        if p == 1:
            factors.insert(0, q)
        else:
            stack.append(p)
            stack.append(q)
    return factors

if __name__ == '__main__':
    print(factorization(200))

生成相近pq

import libnum
import gmpy2
P=libnum.generate_prime(1024)
q=gmpy2.next_prime(p)

RSA密钥生成与读取

公钥生成

from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537

rsa_components = (n, e)
keypair = RSA.construct(rsa_components)
with open('pubckey.pem', 'wb') as f :
    f.write(keypair.exportKey())

私钥生成

from Crypto.PublicKey import RSA

p= 787228223375328491232514653709
q= 814212346998672554509751911073
n= 640970939378021470187479083920100737340912672709639557619757
d= 590103645243332826117029128695341159496883001869370080307201
e= 65537

rsa_components = (n,e,d,p,q)
keypair = RSA.construct(rsa_components)
with open('private1.pem', 'wb') as f :
    f.write(keypair.exportKey())

公钥读取

from Crypto.PublicKey import RSA
with open("pubckey.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)

私钥读取

from Crypto.PublicKey import RSA
with open("private1.pem","rb") as f:
    key = RSA.import_key(f.read())
    print('n = %d' % key.n)
    print('e = %d' % key.e)
    print('d = %d' % key.d)
    print('p = %d' % key.p)
    print('q = %d' % key.q)

共模攻击

共模攻击，也称同模攻击。
同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。
在CTF题目中，就是同一明文，同一n,不同e,进行加密。
m,n相同：e,c不同，且e1和e2互质
==e1 e2互素公约数=1==

[!tip]

根据扩展欧几里德算法对于不完全为0的整数a,b,gcd(a,b)表示a,b的最大公约数。那么一定存在整数x,y使得gcd(a,b)=ax+by

$$
e1 s1+e2 s2=1
$$

简单脚本

import libnum
import gmpy2
s,s1,s2=gmpy2.gcdext(e1.e2)
m=pow(c1.s1,n1)*pow(c2.s2.n2)%n1
print(libnum.n2s(int(m)))

过去脚本

#coding:utf-8
import gmpy2
import libnum

n= 25333966058003377512707481338795714713737652659944601834182685873529702913988641983855700459996104700470621411559153944988952210084014634675583566338568882440708528997808798650962116756969822211586531522430245040013570571043385238601846104615050089457836721437790715225367971106085839523500735480715155424498941150468093083816830215632716244390679417218873179734276657411907216486790815037105108306055794473002315541787461904728375164737225486501009857299717749346279371251245318729951905832578739696926931502225899707226264570557623527701806829827566904224572897378639191756878049342203546309520458672464170859577433
e1= 2333
c1= 11355981897781478907853356911752561659125575027336719997290835661089901154031171698660586203170528368228850895159361637188990782030255983633790580700032092629587631108597144196551438410868034739981960656110887650747325311613900008001234835897835613759692146419080113176963747835592656185435741504176116672174539018089139547795447109458469225330809064539216773123671814859510069089532677704482026169178543062578686794346026774853085101278125763460212801929360456888869350105294595904940799522522144740464043605342348269086324747729288399275079874271519208155039364092577755518532799345651172433227745483422620900776136
e2= 23333
c2= 1326499538902841116411674554069945581390130048432351353260154261863309471312810811160302458644816390944833633923435634961251092531893503039914793217247984595331920909367627316087404934402312358642315675486438968585084964845763881078835787872160374025547400141298650794551970291119975344578667689961134814676553190178139842507675899262024572370313939107080072875068218336255452161407859907308656094331557912187788276334833723893856310434523337557011032081467262457427167978528280339494077785813461280853735266463152709443731638714219391773144349752633555310299318290576258086971373777118482642702020599928071855133041

#共模攻击
#共模攻击函数
def rsa_gong_N_def(e1,e2,c1,c2,n):
    e1, e2, c1, c2, n=int(e1),int(e2),int(c1),int(c2),int(n)
    s = gmpy2.gcdext(e1, e2)
    s1 = s[1]
    s2 = s[2]
    if s1 < 0:
        s1 = - s1
        c1 = gmpy2.invert(c1, n)
    elif s2 < 0:
        s2 = - s2
        c2 = gmpy2.invert(c2, n)
    m = (pow(c1,s1,n) * pow(c2 ,s2 ,n)) % n
    return int(m)
m = rsa_gong_N_def(e1,e2,c1,c2,n)
print(m)
print(libnum.n2s(int(m)))

wiener(维纳)攻击脚本

低解密指数攻击
维纳攻击：e指数很大（理论上d<N** 0.25此攻击起作用）

import gmpy2
import libnum

def continuedFra(x, y):
    """计算连分数
    :param x: 分子
    :param y: 分母
    :return: 连分数列表
    """
    cf = []
    while y:
        cf.append(x // y)
        x, y = y, x % y
    return cf
def gradualFra(cf):
    """计算传入列表最后的渐进分数
    :param cf: 连分数列表
    :return: 该列表最后的渐近分数
    """
    numerator = 0
    denominator = 1
    for x in cf[::-1]:
        # 这里的渐进分数分子分母要分开
        numerator, denominator = denominator, x * denominator + numerator
    return numerator, denominator
def solve_pq(a, b, c):
    """使用韦达定理解出pq，x^2−(p+q)∗x+pq=0
    :param a:x^2的系数
    :param b:x的系数
    :param c:pq
    :return:p，q
    """
    par = gmpy2.isqrt(b * b - 4 * a * c)
    return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):
    """计算列表所有的渐近分数
    :param cf: 连分数列表
    :return: 该列表所有的渐近分数
    """
    gf = []
    for i in range(1, len(cf) + 1):
        gf.append(gradualFra(cf[:i]))
    return gf

def wienerAttack(e, n):
    """
    :param e:
    :param n:
    :return: 私钥d
    """
    cf = continuedFra(e, n)
    gf = getGradualFra(cf)
    for d, k in gf:
        if k == 0: continue
        if (e * d - 1) % k != 0:
            continue
        phi = (e * d - 1) // k
        p, q = solve_pq(1, n - phi + 1, n)
        if p * q == n:
            return d

n= 68781015120012754009149819243839432182753699533745468739333557116438115901358573880902197723852823949505376140916570536753019491036629572363854637530919546688901226752085109196549145599781909847664046508960094447692268230516763088293911965638780888720788954194778424857089535187609738198309161969913567107861
e= 54093680529782962282616750547542407544796590039913570980901028264103594185617926725669901283009540557359666956131385125727959502505561517117179644650419753631214251337533961664493198676862110639584202010794500844074619335752668896589407110076134931918634061631574656816488381501901503924226166074238518619869
c= 30443384983816710270001651296607959522389400057103143909277631290995899073895621701281106228069835965181342091582584186637031613250922961166298411359757600825556083868477673357860585539016515776933117915504873987178857740106223631465737111746470236003857656528610755145017342412306680097140732745012583119076

d=wienerAttack(e, n)
m=pow(c, d, n)
print(libnum.n2s(m).decode())

低加密指数攻击

加密指数指的是e,e一般选取65537，当e很小，可直接破解。
这类攻击在CTF题中，一般是e=3
![[Pasted image 20240609183417.png]]

解密脚本

import gmpy2  
import libnum  

def de(c, e, n):  
    k = 0  
    while True:  
        mm = c + n*k    #明文       
result, flag = gmpy2.iroot(mm, e)   #开方  
        if True == flag:  
            return result  
        k += 1  
n= 14067473525623615859223663589118945198091192669401088734569589535726733244095067264729942915265175903139441309376381225701454902095234966599914234681888481774607095853830772571665038109641511499155604914228117882196188074964226780922239011682486198651997912713999544628177959592818928976240251790858062449396082494272361535640237914373270152455829541596341184902017633404494979208958080467979235974182507427501682492000572071306960595992848840147393057648929439822116261337091431441205378542080755128597543738922210525692259529009107645032171097155449558362749512243918901171631681472217935131865121871798425854707759  
e= 3  
c= 2217344750798294937344050117513831761010547351781457575945714176628679412650463329423466955026804439931765627111856888102133234836914006818023839994342283023142702993182665344445325734299047409223354338948863171846780674244925724334091153701697864918695050507247415283070309  

m=de(c,e,n)  
print(m)  
print(libnum.n2s(int(m)).decode())

低加密指数广播攻击

如果选取的加密指数较低，并且使用了相同的加密指数给一个接受者的群发送相同的信息，那么可以进行广播攻击得到明文。
在CTF中，n、c不同，明文m,e相同，其e比较小。==使用中国剩余定理求解==
==给很多个n，c，并且e很小==

解密脚本1

import libnum
from gmpy2 import invert, gcd, iroot

def op(x):
    res = 1
    for i in x:
        res *= i
    return res

def CRT(m, a):
    assert (len(m) == len(a))
    M = op(m)
    sum = 0
    for m, a in zip(m, a):
        Mi = M // m
        ti = invert(Mi, m)
        sum += a * ti * Mi
    return sum % M
def GCRT(m, a):   #中国剩余定理
    assert (len(m) == len(a))
    curm, cura = m[0], a[0]
    for m, a in zip(m[1:], a[1:]):
        d = gcd(curm, m)
        c = a - cura
        assert (c % d == 0)
        K = c // d * invert(curm // d, m // d)
        cura += curm * K
        curm = curm * m // d
    return cura % curm

e= 23
n= [13700568188515160652483333122748856122721197793561758976293940196437611129096187147049018844770801852491509905633421086860525538786202094426963328030251710764571262136174896745533638173611350459716214924297588461960177050085385463667053134112771796358074472935345700519739991250404101653259068109069693105921388873407341327391535695855870048544246046807524271999074571290297887397122751189238913097314211648891658786959026354758174645247220351373112768023740548658853638361571194694899655444114676642455442372865402013423716810043521278757792135057542028337381224680456644807085272591758332208055210218120184762933993, 12455303951778295101801876746865726762837380068225611327265475119171234220566439286424157465915935073825839673377690927685328334906307316474567186387631653801487281448621083840044622749158794717243547992072439308091388396577613505544620596436291129920864908674330398567591089739953054198863265589615640925745448938637009162522951734388734884333210018733280942210441939903191498896601489219385238879930891399742641138070096026008226581854996694584005317481033177457738077410685570860098544905752983525186623046625831970650060102227916725290755005373441583687173317035035580381484364030548806838563780182184117638395501, 11312913453345524997229175092303757066349809787030135927591246090443816441487008566337534259925791562593802909853876625626317525202428762422138834267165059103366474521447755350822619474026723784588743249816343322663039545930277057837056152601616900790058365628051926865192020616084647924562898079954569875871488048485269581903324695594743584490301132714735102846843035514174635115834382345956826120332925240425711055383445735314612014526078453624636064136731525847521062469732411461240879728208804879621960486763810048962817360272134393185930002946977732438576414921250013379633385546522773969341316069572502067565747, 19273688926871530751707885170718573691217157450567879434223457628340410073625895093788197974441685806302563195850728310991029886375715086122432340760177266985524985445504300034480827487797904941865418089597333968798898696588493471468263648636085443020434703464184815215924633364352735339920297191301112596913193981943417483120540953061378442416926357165828400001655707467493126093621482473840789855669296212432210460828627914111587469312179918093681028472281824867507358588256781382024745011058883359327063772375423890907634909474243733397473408057822868275644578237140525612613960087777442779675214209932962161127943, 25824403380218842654152117237181863815407686057920357548100132783016208234216157331481187013858706620084532009147859360032194662194329147430352381352060599665383607132414222783152103706812942495504805443853663820643284400132519740763181995336671760074736189118849190911417412125673622718186682930944463719251663826122062414169185281402187745799450127860616811214434583738617470847946117017912241156196170781549212311773302997289690360334428053433645188479934679156573770259457673448241437007751122166255146634172359683608410225806629185780976706769275891277564054509652711969428966369382807140328871035548244913540169, 27237916069051621208940446912652352983034283876768722877796629630339066194659652050347720419800886409125794947519574028544026594230991606608793723513349031053967598250588096756917851047427400805606694825815650771281434785207392911507124225263256982256339868047939184615897450178154018301408865653899046967323372600912627209194957697714349971037547547785817038582309482843956504640495722872808769284795831606211370129997371039857944461416328980185572754574947986464294124047090215456723501364524474569642506285260702179251484768225200095243277847312804129809104143492271538375785121251371642879445405237226218130294767, 13761550682262178277138207445908812895938004012620351458812077456012342912081457948142730381037941264721223863482179216010551793547021574285408780459622610402725800322968427850107196669966179328339837806343597136218927944640487794959105652921590477743490006234776475206318254765423468761009179359533340573903819987444132938579714590504929528901380380034611797641640102025769022580055379262631658712636898183456153010636153333354330556615811465638688432337372481631547224635135648075131524783033767896216049834072882777559679890752875405582498757130694817571975439400501682753249614034942783158191876673449277964305873]
c= [10262571808823462518706222972617543597862568988621892788603169566061143066015712397590162941689759961146172690260488971865965270847230222579998032904557938430984766267711048364907947168116473908091952262274847901197798670702630932509348193160049011343984674456154980133706472252009228877741952811774717803218313244040775956381945077497379634101671865923305021804060521682939202170177994307021066512676052755208342422597702905467231418454913781792876325613132181844091995047630699929420681514255787561417787538399764114936771546416271603555435195286433694761222982635917086486380929164535357220194188751490847126159740, 1873760069623225193188031460164577168629510321843511590851589581010158323091884037245625334264450576423497513703748949943402486554235195486945608003604913492410550727032646952732075387833483434157962823847945961417788077590746865603009614636801926695485643494439910816287002493987681839263137321312158281577409606512588038571503481880205375876372759847610515728629030784895468324627007475548811579324164095761843942789779697129082973879068202809855392853491223029896314818656151121278599338954208895547796950391203204627158727359612310869523861493123901912234283765154942764948742461112728821107134608346552771856775, 2985895977894993412250356564280621188757701877004747248029655606908178453788442472530624315824217412687521627124641549636268771426175593603860596969406918746968428475480360839574070154578348252212233965555420185919910549233104881737429986120779245582625147836249604511991694099504498456423355415033891952572068957140136031237587821914297743550751703500164233251775829591163214908665505948671743637428615178406048668071123208829673815143306105215918457316827849469724561259085924020618664008688924504157202910867055508798021785392339533763892777711399815389010578953671416118696256122691527492893238690603105740871718, 880226958648330570665826652923585021064905285913220564535802601268914731939998238851663053132946194395728683681709691206818341165883097568804208974913295560837751365921375933221025439628586836402981502674560586284377581275819082460923772292780487491196858992362166740159608419089452540222602172839570711702715638458570267373629408280794214751990345330692342439212475521544906222647038911039746667297765160642325197077286500302972512842670715220866427191331087678451078964988930072707946282911276517877581001397844626280393814317485128907214187598723285030652543787338988559227984102314239323999288888886062656553567, 2009815427590067013904234705045801411676517862085803426907991060580056876965631979890272588810800230952582542504850877216565503823555945840629024122371840947339558621619080946766065959900677138148030357494710396126783369878070540451138925897438184723977799391715647904517833046633527545658064968373331747651285453005992951298693244135497529999014011663505125408546171884008627711191184419674138689402575260876247393334319284308455639799976027283117878360299913911527890869762030625362974305707352360014964055595635315501016094747111266795155708691399809263809612237731990725856751947329733607523318847566974421507377, 5694700766209667533320463555578774304413921444532095100497641465531621818677278187178007777107102216001903166590706266461389108866563137126658591265596096815630888192401258893389043674230339983362206002697721033273220169349689433933228398864735569502059227668658884754437859192804614688078126017106973898338983058467903273433629800893427045854677794419302456422469488313296020469202479512874455184512957276727018667852597050339727765639174070344434646695283305954814336208535975320481890216924783115781802398152316171967550392347431746885369490458690822632544727994467024208594657404613355215378203965583472028051158, 10292024155412613173825075050556970628998306804602106049394871162726180325842644363271001627039660982320232377250177866906798633433125147372046294230795160430975886694419367570376173140902999001496377201160021928316891425794054040646925354276987039659647583093660753953920769021487949471906220620446860851971969844544591399518592683848757784465531598787547279741438244737906014906621222662915117890417807671575763023265920422409800110274912550502682376498609611973173660997965660328963204286476887664127188442751055758474381180365051193094521479396706496869721757475497142256079170254820437945136475911435012491537989]

m = CRT(n, c)
m1 = iroot(m, e)  # 开e次方
print(m1)
print(libnum.n2s(int(m1[0])))

解密脚本2

import binascii,gmpy2
from functools import reduce

import libnum

def CRT(mi, ai):
    assert(reduce(gmpy2.gcd,mi)==1)
    assert (isinstance(mi, list) and isinstance(ai, list))
    M = reduce(lambda x, y: x * y, mi)
    ai_ti_Mi = [a * (M // m) * gmpy2.invert(M // m, m) for (m, a) in zip(mi, ai)]
    return reduce(lambda x, y: x + y, ai_ti_Mi) % M

e= 23
n= [13700568188515160652483333122748856122721197793561758976293940196437611129096187147049018844770801852491509905633421086860525538786202094426963328030251710764571262136174896745533638173611350459716214924297588461960177050085385463667053134112771796358074472935345700519739991250404101653259068109069693105921388873407341327391535695855870048544246046807524271999074571290297887397122751189238913097314211648891658786959026354758174645247220351373112768023740548658853638361571194694899655444114676642455442372865402013423716810043521278757792135057542028337381224680456644807085272591758332208055210218120184762933993, 12455303951778295101801876746865726762837380068225611327265475119171234220566439286424157465915935073825839673377690927685328334906307316474567186387631653801487281448621083840044622749158794717243547992072439308091388396577613505544620596436291129920864908674330398567591089739953054198863265589615640925745448938637009162522951734388734884333210018733280942210441939903191498896601489219385238879930891399742641138070096026008226581854996694584005317481033177457738077410685570860098544905752983525186623046625831970650060102227916725290755005373441583687173317035035580381484364030548806838563780182184117638395501, 11312913453345524997229175092303757066349809787030135927591246090443816441487008566337534259925791562593802909853876625626317525202428762422138834267165059103366474521447755350822619474026723784588743249816343322663039545930277057837056152601616900790058365628051926865192020616084647924562898079954569875871488048485269581903324695594743584490301132714735102846843035514174635115834382345956826120332925240425711055383445735314612014526078453624636064136731525847521062469732411461240879728208804879621960486763810048962817360272134393185930002946977732438576414921250013379633385546522773969341316069572502067565747, 19273688926871530751707885170718573691217157450567879434223457628340410073625895093788197974441685806302563195850728310991029886375715086122432340760177266985524985445504300034480827487797904941865418089597333968798898696588493471468263648636085443020434703464184815215924633364352735339920297191301112596913193981943417483120540953061378442416926357165828400001655707467493126093621482473840789855669296212432210460828627914111587469312179918093681028472281824867507358588256781382024745011058883359327063772375423890907634909474243733397473408057822868275644578237140525612613960087777442779675214209932962161127943, 25824403380218842654152117237181863815407686057920357548100132783016208234216157331481187013858706620084532009147859360032194662194329147430352381352060599665383607132414222783152103706812942495504805443853663820643284400132519740763181995336671760074736189118849190911417412125673622718186682930944463719251663826122062414169185281402187745799450127860616811214434583738617470847946117017912241156196170781549212311773302997289690360334428053433645188479934679156573770259457673448241437007751122166255146634172359683608410225806629185780976706769275891277564054509652711969428966369382807140328871035548244913540169, 27237916069051621208940446912652352983034283876768722877796629630339066194659652050347720419800886409125794947519574028544026594230991606608793723513349031053967598250588096756917851047427400805606694825815650771281434785207392911507124225263256982256339868047939184615897450178154018301408865653899046967323372600912627209194957697714349971037547547785817038582309482843956504640495722872808769284795831606211370129997371039857944461416328980185572754574947986464294124047090215456723501364524474569642506285260702179251484768225200095243277847312804129809104143492271538375785121251371642879445405237226218130294767, 13761550682262178277138207445908812895938004012620351458812077456012342912081457948142730381037941264721223863482179216010551793547021574285408780459622610402725800322968427850107196669966179328339837806343597136218927944640487794959105652921590477743490006234776475206318254765423468761009179359533340573903819987444132938579714590504929528901380380034611797641640102025769022580055379262631658712636898183456153010636153333354330556615811465638688432337372481631547224635135648075131524783033767896216049834072882777559679890752875405582498757130694817571975439400501682753249614034942783158191876673449277964305873]
c= [10262571808823462518706222972617543597862568988621892788603169566061143066015712397590162941689759961146172690260488971865965270847230222579998032904557938430984766267711048364907947168116473908091952262274847901197798670702630932509348193160049011343984674456154980133706472252009228877741952811774717803218313244040775956381945077497379634101671865923305021804060521682939202170177994307021066512676052755208342422597702905467231418454913781792876325613132181844091995047630699929420681514255787561417787538399764114936771546416271603555435195286433694761222982635917086486380929164535357220194188751490847126159740, 1873760069623225193188031460164577168629510321843511590851589581010158323091884037245625334264450576423497513703748949943402486554235195486945608003604913492410550727032646952732075387833483434157962823847945961417788077590746865603009614636801926695485643494439910816287002493987681839263137321312158281577409606512588038571503481880205375876372759847610515728629030784895468324627007475548811579324164095761843942789779697129082973879068202809855392853491223029896314818656151121278599338954208895547796950391203204627158727359612310869523861493123901912234283765154942764948742461112728821107134608346552771856775, 2985895977894993412250356564280621188757701877004747248029655606908178453788442472530624315824217412687521627124641549636268771426175593603860596969406918746968428475480360839574070154578348252212233965555420185919910549233104881737429986120779245582625147836249604511991694099504498456423355415033891952572068957140136031237587821914297743550751703500164233251775829591163214908665505948671743637428615178406048668071123208829673815143306105215918457316827849469724561259085924020618664008688924504157202910867055508798021785392339533763892777711399815389010578953671416118696256122691527492893238690603105740871718, 880226958648330570665826652923585021064905285913220564535802601268914731939998238851663053132946194395728683681709691206818341165883097568804208974913295560837751365921375933221025439628586836402981502674560586284377581275819082460923772292780487491196858992362166740159608419089452540222602172839570711702715638458570267373629408280794214751990345330692342439212475521544906222647038911039746667297765160642325197077286500302972512842670715220866427191331087678451078964988930072707946282911276517877581001397844626280393814317485128907214187598723285030652543787338988559227984102314239323999288888886062656553567, 2009815427590067013904234705045801411676517862085803426907991060580056876965631979890272588810800230952582542504850877216565503823555945840629024122371840947339558621619080946766065959900677138148030357494710396126783369878070540451138925897438184723977799391715647904517833046633527545658064968373331747651285453005992951298693244135497529999014011663505125408546171884008627711191184419674138689402575260876247393334319284308455639799976027283117878360299913911527890869762030625362974305707352360014964055595635315501016094747111266795155708691399809263809612237731990725856751947329733607523318847566974421507377, 5694700766209667533320463555578774304413921444532095100497641465531621818677278187178007777107102216001903166590706266461389108866563137126658591265596096815630888192401258893389043674230339983362206002697721033273220169349689433933228398864735569502059227668658884754437859192804614688078126017106973898338983058467903273433629800893427045854677794419302456422469488313296020469202479512874455184512957276727018667852597050339727765639174070344434646695283305954814336208535975320481890216924783115781802398152316171967550392347431746885369490458690822632544727994467024208594657404613355215378203965583472028051158, 10292024155412613173825075050556970628998306804602106049394871162726180325842644363271001627039660982320232377250177866906798633433125147372046294230795160430975886694419367570376173140902999001496377201160021928316891425794054040646925354276987039659647583093660753953920769021487949471906220620446860851971969844544591399518592683848757784465531598787547279741438244737906014906621222662915117890417807671575763023265920422409800110274912550502682376498609611973173660997965660328963204286476887664127188442751055758474381180365051193094521479396706496869721757475497142256079170254820437945136475911435012491537989]

m=gmpy2.iroot(CRT(n, c), e)[0]
print(m)
print(libnum.n2s(int(m)))

N不互素（共享素数）

两个n里使用有相同的素数p或q在CTF中，同样一个e(一般为65537)和m,有两个或多个n和c时，那么n之间可能是共享素数==关键在于多个n使用相同q或p，e为65537==

解密

import libnum
import gmpy2

e= 65537
n1= 18851781425565649500243914718895527060598553785142033499277947796047289729069551538151421839511239897691881228121437622923274745439286192958624933347473814433650645821240330239352230328910532686189064529002598986350545013596873280380093139589440286483854335646063005690269032198568724965964443111093291700142910652223408636268615176273268372177721667944316123253596652992256076572634227395015036348109972259736684061785035583511127926569341967394058493301139935304361924639075754092181040235419401702148068770694697982444290753353433701503833775179671108406498799549700127209151389161427718168658930877516526900193773
n2= 24141384186719901100738328229558939321137195844627407412035205930880546126459260897433418685279927024995699136588216700770429628894224051287181657357533218989737870319139269421990248988961435374202640406264110282763206906390508271179764960952342404379846442988489435158217691170804372863828966379599925114485971708200189788312061335938149982724447336254731731196164294152411281627551943972751739099703406466680639123738668207648503911709799873188331259979032169198913999856215096219340617703116234922400948884716827963616800355410477122406692338452507358998811789750057925245184372948089354754021196407808558611706347
c1= 11233930138929485738604185458820792679941706517184575056860307907280050814616639358486313129298273947905894904145194035804995663173314907762677924041275132974029028894644172713486633713023630611556983846927634063704894533048653309657581762974450289360550659261899944333557732087882069544235529266455787027619668939220511057340231613645208599303911724024926701608537602920797245075262273603379467945283128416767718651714209330369788240996832207630345743245279821753430782200336283582459635492184924556145031704499178500242816865275291936063430100028447772122941596704727728675661250380470986371668037469383671505328135
c2= 5585224206647236865248808202221713289466135149339680308821203835812670001259895780508640505222648200259525489427033258746992319005320440650548405653844536422632581252608192223771882550003217335273112474383014796651892287737753603533030776710121680439078567046997872719450037145665867123925472406058893384600128119493338790196284996386511009366274826447064392594100457497289556291407982935292829015102796178711091471748295065093460144885719356062242014650190112796869173536886083200906303200902844575328314123662659807283984619970501020349836850699532193026247740142876327310689901499496665093919484517214474842110431

#求最大公约数
q=gmpy2.gcd(n1,n2)
p1=n1//q

phi_n=(q-1)*(p1-1)
#求逆元d
d1=libnum.invmod(e,phi_n)
m=pow(c1,d1,n1)
print(m)
#数字转字节，转字符串
print(libnum.n2s(int(m)).decode())

dp泄露

dp=d%(p-1)

解密

#coding:utf-8
import libnum
import gmpy2

n= 15490329974794812647207350945845678224681604428642220566423366180973839697096441619340018253695472604335938643849069014103520861300713053955205392905536446156153192076633656788424185734898016745641378430506574498111680248029123341493733599302123100131134215957579162168779228208387783035893621162016993340603475960735061572761512755519616410410615413820180757126318567325096339342686253738778178380191340135516056457473854126752188188261914055391966730674861017432904735293451031131827880629989269835970170038295168392442835892108945315382078025510997711116410638765048886317360842562784200384045644008789130370444983
e= 65537
dp= 92421914522602787051376990773545034723755500322946639408033747477366773088952064561196722681757327451210117825346237003629597066505402384880737033044776720946764227004188812078355462119361676746112866393394866072449432108301690846327127554699521545673830710939287951837844749172755258073462248214264511338895
c= 11917967705200196530423914441613144297148147672566202863977167024519218321836386637302409557947445841293888462405994683655441879000427977086221906497225533946193332303182079068462781262341197088906792898634398410298474823088739257515556595214077227746604247505450334512424047100626106474291190033258919062850451435841454816600402372026810570127115167968899329724894556092798669018218440148846597174016217159034241427361756697433952800424383010684502324285145303400856470193420837017178412747680690628590204528459258189973779463979907863227915782407651254796209362605706066438960631045833533860845111845422613428738602

for i in range(1,65537):  #爆破
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break
print(p)
print(q)
phi_n= (p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
flag=libnum.n2s(int(m)).decode()
print(flag)

推导过程

题目解析:
![[Pasted image 20240610202507.png]]

已知：

c = m^e mod n
m = c^d mod n
ϕ(n)=(p−1)*(q−1)
d∗e ≡ 1 mod ϕ(n)
dp = d mod (p−1)

由上式可以得到 

dp*e≡d*e mod (p−1)

因此可以得到 

式1：d∗e=k∗(p−1)+dp∗e
式2：d∗e≡1 mod phi

式1带入式2

=> k∗(p−1)+dp∗e ≡1 mod phi

=> k∗(p−1)+dp∗e ≡1 mod (p−1)∗(q−1)

=> k1∗(p−1)+dp∗e = k2*(p−1)∗(q−1)+1

=> dp*e =  k2*(p−1)∗(q−1)+1-k1∗(p−1)+dp∗e

=> dp*e = (p-1)*[k2*(p-1)-k1]+1

因dp<p−1（dp是d//（p-1）的余数，dp<p−1）

所以e > k2∗(q−1)−k1

假设 x=k2∗(q−1)−k1

x的范围为 (0,e)

x∗(p−1)+1=dp∗e

求出p-1方法，遍历(0,e)的范围，其中肯定有一个p可以被n整除，那么求出p和q

dpdq

一般情况

#前提m<p,m<q
m=pow(c,dp,p)
#或者
m=pow(c,dq,q)

解密(m>p,m>q)

# coding=utf-8
import gmpy2
import libnum

def decrypt(dp,dq,p,q,c):
    InvQ = gmpy2.invert(q, p)
    mp = pow(c, dp, p)
    mq = pow(c, dq, q)
    m = (((mp-mq)*InvQ) % p)*q+mq
    print(libnum.n2s(int(m)).decode())

p= 160332148422085773419118366054725936852233416334843123745197905865814122767542980683547268180832158164485150298039693727719040683372172258525148659296087240380682418673910965969383538696724039000114078510939033236731476700182949760779821042982194738324421029616780752077145649691266297077244661585947836997447
q= 148424511925430832355285085986622242653116164650119278601839811809456838348201308360579207172541711367335049779204390510911294031319604192881139002646252381246691575112024047502962776542023275076827456857946499013733968522162634588753330857821421229306405469212854327011240808908334404955299250060931240865821
dq= 46499718919891753512042256824043332562579628188599554881257534157373206051013462063558177543473555667701042801266834703603013397791386747764400964376350060145521940586234916815399419075649204020285050341140996959732454059493770135591854817473937175643058380668604376797759987312600851466228301604453060674993
dp= 142333710655003285129381975633061553108365353347897720974344479656881847851071160049571693284111493690735707224010091720382284617217647771503015838348510851051285580945849520119912938971503190396671148935203517916795662212439446680229030750273953490024181996476865040448118374338738013091140796970725623029913
c= 19717919131356145411002342007533511479254120775597684622452661875292805564648015749422307039514664862428413419529876049533096947970606477676695854787457286807502628964582922773374784879459806551819337741730331777937597915727889640104583136339578788518904647309084873362461758500783634423921343109980901514994298280728150961559886893338458119937441920391275957965781890308011172861718172757876950159723089326843019779174406022143147201642738466470809603008292152193968160973116769118512212438656127645018486302418482079051867180606083540035964208124143457540388206274742292869004756069240519187723267661857029470809099

decrypt(dp,dq,p,q,c)

AMM 算法

p和q是相邻的2个素数，这可以对n开平方，在开平方数附近查询下一个素数即可分解得到p和q

e=33也有问题，e与p-1有公因数，导致无法正常求d，使用AMM算法可求出所有满足条件的m,再匹配关键字符得到flag，也可依次开方

import gmpy2  
import random  
import math  
import libnum  
import time  
from Crypto.Util.number import bytes_to_long, long_to_bytes  

n = 20157817216833049974118616679190322575901864730668507144482957326182327740713453136333068539106100083027097757551546799575541531293312944887561483280916726369016319612934944450526019975934692298293195561411060477885773405036861008621958822147021639661752191557841624683504007344816984603147270693016174228339440038288427589158890266471648249125569765932533982185987755634089743765749564333612512194933232263756745378109393583291224010700913573540529420652068898993898479078127254056483844853346390136211506294067721897916177680505768950977554254296490057308239156157838713269319343550186321669135205346102566222209669  

p1 = gmpy2.iroot(n, 2)[0]  
while n % p1 != 0:  
    p1 = gmpy2.next_prime(p1)  
p = p1  
q = n / p  

# print(p,q)  
assert (n == p * q)  
c = 5550850995648431308122724561862321298330352966504532253941573060435227523644220681378247173522846277972751332156705955942551071366281109518855989368023554577347696287379088984498887267023431403241260985825192081189555696375201465274976430133175304403838370385321814599530029586724109782046451141042893149621734986470429809900193355827277275722227551304063436655735688781909919640024815423934941154264458525685654968501198690422227441772911516150511832369493008699728485535931462629750837466741030971574567414557223186771992335515743296998159321297009298268426970949419821980177125657422472184449785482615837014554125  
e = 33  

def GF(a):  
    global p  
    p = a  

def g(a, b):  
    global p  
    return pow(a, b, p)  

def AMM(x, e, p):  
    GF(p)  
    y = random.randint(1, p - 1)  
    while g(y, (p - 1) // e) == 1:  
        y = random.randint(1, p - 1)  
        print(y)  
    print("find")  
    # p-1 = e^t*s  
    t = 1  
    s = 0  
    while p % e == 0:  
        t += 1  
        print(t)  
    s = p // (e ** t)  
    print('e', e)  
    print('p', p)  
    print('s', s)  
    print('t', t)  
    # s|ralpha-1  
    k = 1  
    while ((s * k + 1) % e != 0):  
        k += 1  
    alpha = (s * k + 1) // e  
    a = g(y, (e ** (t - 1)) * s)  
    b = g(x, e * alpha - 1)  
    c = g(y, s)  
    h = 1  
    #  
    for i in range(1, t - 1):  
        d = g(b, e ** (t - 1 - i))  
        if d == 1:  
            j = 0  
        else:  
            j = -math.log(d, a)  
        b = b * (g(g(c, e), j))  
        h = h * g(c, j)  
        c = g(c, e)  
    # return (g(x, alpha * h)) % p  
    root = (g(x, alpha * h)) % p  
    roots = set()  
    for i in range(e):  
        mp2 = root * g(a, i) % p  
        roots.add(mp2)  
    return roots  

def check(m):  
    if 'CnHongke' in m:  
        print(m)  
        return True  
    else:  
        return False  

mps = AMM(c, e, p)  
for mpp in mps:  
    solution = str(long_to_bytes(mpp))  
    if check(solution):  
        print(solution)  

# CnHongke{a5c3895e-cb83-47aa-9674-03f8644b24c0}