AES加密

给的是一串base64,直接解密后会有Salted__字样，这主要是通过openssl加密如果不带base64就会出现Salted字段打头,以U2FsdGVkX1打头的主要是rabbit，AES，DES

rsa大整数分解

factor查询

yafu暴力破解

.\yafu-x64.exe "factor(6)"

[黑盾杯 2020]Factor

这题的q和p不互素，即n解出来有三位数

可以找一个乘积和e互素的从而计算m，flag较小只取两个因子就可以解出来

import gmpy2
from Crypto.Util.number import long_to_bytes
p= 17100682436035561357
q= 17172929050033177661
r = 11761833764528579549
n= 3454083680130687060405946528826790951695785465926614724373
e = 3
c = 1347530713288996422676156069761604101177635382955634367208
phi_n1 = [(q-1)*(r-1),(p-1)*(q-1),(p-1)*(r-1)]

# for phi_n in phi_n1:
#     print(gmpy2.gcd(e,phi_n))
print(phi_n1[0])
d=gmpy2.invert(e,phi_n1[0])
m = pow(c,d,q*r)
print(long_to_bytes(m))

e和phi不互素

通过AMM暴力求解循环域上开根

#sage
e=4
p= 182756071972245688517047475576147877841
q= 305364532854935080710443995362714630091
c= 14745090428909283741632702934793176175157287000845660394920203837824364163635
n= 55807222544207698804941555841826949089076269327839468775219849408812970713531

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 = hex(CRT_list([int(x), int(y)], [p, q]))[2:]
        print(solution)
        if solution.startswith('4e53'):#4e53 十六进制NS
            print(solution)

正常计算

首先算出phi

$\varphi(n)=\prod_{i=1}^{r} p_{i}^{k_{i}-1}\left(p_{i}-1\right)=\prod_{p\mid n} p^{\alpha_{p}-1}(p-1)=n\prod_{p\mid n}\left(1-\frac{1}{p}\right)$

然后算e mod phi的逆，再pow(c,d,n)就行了

共模攻击、低加密指数攻击、dp泄露

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


# e1 = 3 低加密指数分解攻击 求m1
e1 = 3
N1 = 123814470394550598363280518848914546938137731026777975885846733672494493975703069760053867471836249473290828799962586855892685902902050630018312939010564945676699712246249820341712155938398068732866646422826619477180434858148938235662092482058999079105450136181685141895955574548671667320167741641072330259009
c_powmod_msg1_e1_N1 = 19105765285510667553313898813498220212421177527647187802549913914263968945493144633390670605116251064550364704789358830072133349108808799075021540479815182657667763617178044110939458834654922540704196330451979349353031578518479199454480458137984734402248011464467312753683234543319955893
# N1 比 powmod_msg1_e1_N1 来的大 所以开三次方可以直接获得的msg1
# e = 3的时候 是进行低加密指数分解攻击 m^e>n
# c = powmod(m, e, n1) m^e = c + k*n1  => m = iroot(c + k*n1, e)
k = 0
while 1:
    ret = gmpy2.iroot(c_powmod_msg1_e1_N1 + k*N1, e1)
    if(ret[1] == True): # 能够有效开根
        m1 = ret[0]
        break
    k += 1

# 共模攻击 N2 求m2
e2 = 17
e3 = 65537
N2 = 111381961169589927896512557754289420474877632607334685306667977794938824018345795836303161492076539375959731633270626091498843936401996648820451019811592594528673182109109991384472979198906744569181673282663323892346854520052840694924830064546269187849702880332522636682366270177489467478933966884097824069977
c_powmod_msg2_e2_N2 = 54995751387258798791895413216172284653407054079765769704170763023830130981480272943338445245689293729308200574217959018462512790523622252479258419498858307898118907076773470253533344877959508766285730509067829684427375759345623701605997067135659404296663877453758701010726561824951602615501078818914410959610
c_powmod_msg2_e3_N2 = 91290935267458356541959327381220067466104890455391103989639822855753797805354139741959957951983943146108552762756444475545250343766798220348240377590112854890482375744876016191773471853704014735936608436210153669829454288199838827646402742554134017280213707222338496271289894681312606239512924842845268366950

# 共模攻击时， gcd(e1, e2) = 1 => 存在s1 s2使得 e1*s1+e2*s2 = 1  s1与s2一正一负
# 并且有m = (c1^s1)*(c2^s2)
# gmpy2.gcdext(e1,e2) 用于求式子 e1*x+e2*y=gcd(e1,e2) 的解
#   Return a 3-element tuple (g,s,t) such that
#         g == gcd(a,b) and g == a*s + b*t

def rsa_mod_same_N(e1, c1, e2, c2, n):
    s, s1, s2 = gmpy2.gcdext(e1, e2)
    # print(s, s1, s2)
    m = gmpy2.mod(gmpy2.powmod(c1, s1, n)*gmpy2.powmod(c2,s2,n), n)
    return m

m2 = rsa_mod_same_N(e2, c_powmod_msg2_e2_N2, e3, c_powmod_msg2_e3_N2, N2)

# 高位泄露 求m3
N3 = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147
c_powmod_msg3_e3_N3 = 59213696442373765895948702611659756779813897653022080905635545636905434038306468935283962686059037461940227618715695875589055593696352594630107082714757036815875497138523738695066811985036315624927897081153190329636864005133757096991035607918106529151451834369442313673849563635248465014289409374291381429646
p3_left_200 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902

'''
# 利用在线sage计算器 https://sagecell.sagemath.org/ 运行如下代码
#sage

#p4已知高位
p4 = 7117286695925472918001071846973900342640107770214858928188419765628151478620236042882657992902
n = 113432930155033263769270712825121761080813952100666693606866355917116416984149165507231925180593860836255402950358327422447359200689537217528547623691586008952619063846801829802637448874451228957635707553980210685985215887107300416969549087293746310593988908287181025770739538992559714587375763131132963783147

#全位数
pbits = 512

#缺省位数
kbits = pbits - p4.nbits()  #nbits()位数
print (p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))

f = x + p4
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]
p = p4+x0
print ("p: ", hex(int(p)))
assert n % p == 0

# 输出： 312
# 输出：
312
p:  0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7
'''
p3 = int('0xda5f14bacd97f5504f39eeef22af37e8551700296843e536760cea761d334508003e01b886c0c69b4365759fb42a3faaf0c8888106bb9dbb1137769a37d191a7', 16)
q3 = N3 // p3
phin3 = (p3 - 1) * (q3 - 1)
d3 = gmpy2.invert(e3, phin3)
m3 = gmpy2.powmod(c_powmod_msg3_e3_N3, d3, N3)

flag = long_to_bytes(m1) + long_to_bytes(m2) + long_to_bytes(m3)

print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(long_to_bytes(m3))
# md5.new(text).hexdigest() == flag[6:-1] 题目使用了md5进行加密
print(hashlib.md5(flag).hexdigest())

ctf-crypto