[BUUCTF-crypto]writeup【loading】

[BUUCTF-crypto]writeup

数学

[WUSTCTF2020]大数计算

Note：理解问题，题目说要十六进制，前8位不知道是取十进制的前八位然后转换还是取十六进制的前八位，所以（错误就得多试试

a = math.factorial(2020)
print(a)
print(hex(int(str(a)[:8])))

x = pow(520,1314) + pow(2333,666)
print(x)
print(hex(int(str(x)[:8])))

宇宙终极问题：x³＋y³＋z³＝42

(-80538738812075974)³ + 80435758145817515³ + 12602123297335631³ = 42

part-4，简单的积分，计算面积即可，再加36得520

编码

鸡藤椒盐味 【汉明码】

设将要进行检测的二进制代码为n位，为使其具有纠错能力，需要再加上k位的检测位，组成n+k位的代码。那么，新增加的检测位数k应满足：

2k≥n+k+1或2k-1≥n+k

古典

[INSHack2018]Crypt0r part 1【tcp流+简单替换】

给出pcap文件

使用wireshark打开，并分析tcp数据流

quipquip直接频率分析得到的结果不太对，再仔细观察可能用到的为第二行中的

def replacement(s,cipher):
    # s为m中对应的字母
    m = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
    x = string.ascii_letters.maketrans(s, m)
    print(cipher.translate(x))
    
s = 'PMSFADNIJKBXQCGYWETOVHRULZ'
s += s.lower()
replacement()

[UTCTF2020]basic-crypto

打开文件是二进制形式，先转十六进制，再转ASCII试试

提示很明显base64

提示移位以及Roman，试试凯撒

提示进行词频分析

达芬奇密码 【换位】

根据电影简介，看到斐波那契数列

观察给出的一列数字，为32位，flag也是32位，

写一个函数，输出32个斐波那契数列的数

def fib(n):
    if n == 0 or n == 1:
        return 1
    return fib(n-1) + fib(n-2)

for i in range(50):
    print(fib(i),end=' ')

原文flag通过移位得到密文c

第0位均为1，位置不变

原fib数列的233（12位）变换到第1位

因此只需要找到f在原数列哪个位置，再把c对应的数字放回原位即可，注意有两个1，而第0位不变，因此可以把第0位修改为0或其他没有冲突的数字

fib = "0 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309"

f = "0 233 3 2584 1346269 144 5 196418 21 1597 610 377 10946 89 514229 987 8 55 6765 2178309 121393 317811 46368 4181 1 832040 2 28657 75025 34 13 17711"

c = "36968853882116725547342176952286"

m = ['3']*32

fib = fib.split(' ')
f = f.split(' ')

for i in range(len(f)):
    m[fib.index(f[i])] = c[i]
for i in m:
    print(i,end='')

?[UTCTF2020]hill

未知密钥，猜测

s='wznqcaduqopfkqnwofDbzgeu'
#未给密钥的自己猜测
flag_pre='utflag'
def getit(a1,b1,c1,a2,b2,c2,a3,b3,c3):
    for i in range(26):
        for j in range(26):
            if (a1 * i + b1 * j) % 26 == c1 and (a2 * i + b2 * j) % 26 == c2 and (a3 * i+b3*j) % 26 == c3:
                return (i,j)
x1=getit(22,25,20,13,16,5,2,0,0)
x2=getit(22,25,19,13,16,11,2,0,6)
import string
flag=''
for i in range(0, len(s),2):
    flag+=string.ascii_letters[(x1[0]*string.ascii_letters.index(s[i])+x1[1]*string.ascii_letters.index(s[i+1]))%26]
    flag+=string.ascii_letters[(x2[0]*string.ascii_letters.index(s[i])+x2[1]*string.ascii_letters.index(s[i+1]))%26]
print(flag)

[XNUCA2018]baby_crypto【重合指数、词频分析】

题目:26个字母用0-25分别表示，有两串密钥，长度未知，然后一个用作乘数，一个用作加数对明文进行加密

https://blog.csdn.net/weixin_44110537/article/details/107947158

块密码

[ACTF新生赛2020]crypto-aes

因为

key=os.urandom(2)*16
iv=os.urandom(16)

key是32bytes,256bits ；iv是16bytes ,128bits

由于os.urandom（size）

参数： size:字符串随机字节的大小 返回值：该方法返回一个字符串，该字符串表示适合加密使用的随机字节。

所以可以根据key的高128位得到key值，低128位和结果异或便得到iv

最后进行解密即可

from Crypto.Cipher import AES
import os
from gmpy2 import*
from Crypto.Util.number import*

xor = 91144196586662942563895769614300232343026691029427747065707381728622849079757
enc_flag = b'\x8c-\xcd\xde\xa7\xe9\x7f.b\x8aKs\xf1\xba\xc75\xc4d\x13\x07\xac\xa4&\xd6\x91\xfe\xf3\x14\x10|\xf8p'
out = long_to_bytes(xor)
print(out)
key = out[:16]*2
print(key)
iv = bytes_to_long(key[16:])^bytes_to_long(out[16:])
print(iv)
iv = long_to_bytes(iv)
print(iv)
aes = AES.new(key,AES.MODE_CBC,iv)
flag = aes.decrypt(enc_flag)
print(flag)

[AFCTF2018]MyOwnCBC【AES-CBC】

加密过程是用上一级的密文，作为下一次加密的密钥key,所以初始密钥key可以知道就是题目给的密文前32个

[美团CTF]

[ACTF新生赛2020]crypto-des

c语言中数据在内存中的存储（大小端）

有轮密钥，直接解密即可

流密码

?[AFCTF2018]你听过一次一密么？

一次一密（One-Time-Pad）：xor key 明文多长，密文就多长（适合少量明文消息）

Many-Time-Pad攻击：多个明文异或同样的key

https://www.ruanx.net/many-time-pad/

攻击思想：对于每一条密文Ci，拿去异或其他所有密文。然后去数每一列有多少个英文字符，作为“Mi在这一位是空格”的评分。依据评分从大到小排序，依次利用 “某个明文的某一位是空格” 这种信息恢复出所有明文的那一列。如果产生冲突，则舍弃掉评分小的

修复语句太绝了

？[De1CTF2019]xorz 【频率分析/break repeating-key】

法一：流密码

参考

https://www.anquanke.com/post/id/161171#h3-

http://socold.cn/index.php/archives/65/

一.猜测密钥长度

1.暴力破解：

https://www.ruanx.net/many-time-pad/

给的是 m[i]⊕k[i]⊕s[i], 其中 s 已知，故实际上我们拿到了 m[i]⊕k[i]. 在这里 k 是有周期的，且周期不超过38。如果知道了 k 的周期，那么用 Many-Time-Pad 就可以成功攻击。由于 len(key) 并不大，从大到小枚举 len(key)，肉眼判断是否为flag即可。最后发现 len(key)=30 是满足要求的。

但是这种方法过于耗时费力

2.汉明距离：一组二进制数据变成另一组数据所需的步骤数。对两组二进制数据进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。

• 根据扩展资料：

  • 两个以ascii编码的英文字符的汉明距离是2-3之间，也就是说正常英文字母的平均汉明距离为2-3（每比特），任意字符（非纯字母）的两两汉明距离平均为4。

  • 正确分组的密文与密文的汉明距离等于明文与明文的汉明距离（可以通过按正确密钥长度分组的密文与密文异或等于明文与明文异或证明）

    因此，当我们使用了正确的密钥长度后，两两字母进行计算汉明距离，那么这个值应该是趋于最小。为了增加效率，我们不需要对每一对分组都计算汉明距离，只需取出前几对就可说明问题。当然为了排除偶然误差，结果不应该只取最小的那一个密钥长度，而是酌情多取几组

二.根据猜出的密文长度进行解密

两种方法：

• 合理利用明文的空格

  在使用异或加密的形式下，使用相同密钥加密的明文和秘文间存在这个规律，密文和密文异或等于明文和明文异或,并且二者的汉明距离一样。

  空格和所有小写字母异或结果是相应的大写字母，空格和所有大写字母异或是相应的小写字母。

  

  

  1. 使用取模运算把密文分成n个分组（其中n是密钥长度），如此以来，我们就有了n个独立的凯撒加密式的密文组（因为每个分组里面的值是使用同一个密钥字节明文异或）。这样就把问题简化成了破解n个独立的凯撒加密模式的单字节抑或密码方式。这一步可以直接使用爆破，但是效率不高。我们采取另一种姿势。
  2. 将2中的每个分组做如下的操作：每个分组做嵌套循环，内循环，外循环。设置外循环计数值possible*space=0，maxpossible=0，设置内循环计数值maxpossible=0,依次取出每个分组中的每一个字节做与其他字节两两抑或进行内循环，如果结果是字母，我们就把内循环计数值maxpossible+1,在每个内循环结束后进行maxpossible的更新（与内循环maxpossible做对比），并记录当前字节的位置到possiblespace，然后外循环继续。直至遍历完所有的字节。取出maxpossible对应的字节位置possible*space处的字节码，我们把它对应的明文假设成空格（根据之前的讨论）然后将该位置的字节和0x20（空格）异或;找出相应位置的密钥字节。

3. 重复2中的步骤，依次根据每个分组找出每位的密钥字节，至此密钥破解完毕

4. 将找出的密钥用于破解密文。当密文足够多，可以发现破解的准确率很高，基本可以做到无差别破解。

词频分析

https://codeleading.com/article/68135872581/

？[SUCTF2019]MT【移位】

https://blog.csdn.net/m0_49109277/article/details/117324488

[AFCTF2018]tinylfsr

根据给出的文件，发现两次文件加密

• plain->cipher
• flag->flag_encode

查看encrypt.py，加密方式为

• 前一部分：key与plain的前一部分xor
• 后一部分：lfsr生成的密钥流与plain的后一部分xor

进一步分析，可以发现key与mask位数是相同的，看了一下mask的位数是二进制64位，那么key的位数就是16进制16位，也就是8位ASCII字符.

(不知道key长度的话，也可以遍历一下，再用该key对plain加密看是否与cipher相同)

cip = open('cipher.txt', 'rb').read()
msg = open('Plain.txt', 'rb').read()

print(codecs.encode(strxor(cip, msg)[:8], 'hex'))

接下来可以生成lfsr的密钥流，再依次解密（R要初始化为key）

key = '0123456789abcdef'
R = int(key, 16)
mask = 0b1101100000000000000000000000000000000000000000000000000000000000


def lfsr(R, mask):
    # 左移1位：保留末尾 63 位，在最后添加一个0
    output = (R << 1) & 0xffffffffffffffff

    # i：保留 R 的前 0、1、3、4位
    i = (R & mask) & 0xffffffffffffffff

    lastbit = 0
    while i != 0:
        lastbit ^= (i & 1)
        i = i >> 1
    # lastbit：统计 i 里面有多少个1, 奇数个则为1, 偶数个则为0

    # output: R 左移1位，再添加 lastbit
    output ^= lastbit
    return (output, lastbit)


cip = open('flag_encode.txt', 'rb').read()
a = ''.join([chr(int(b, 16)) for b in [key[i:i + 2] for i in range(0, len(key), 2)]])

ans = ""

for i in range(len(a)):
    ans += (chr((cip[i] ^ ord(a[i]))))

lent = len(cip)

for i in range(len(a), lent):
    tmp = 0
    for j in range(8):
        (R, out) = lfsr(R, mask)
        tmp = (tmp << 1) ^ out
    ans += (chr(tmp ^ cip[i]))

print(ans)

秘密共享的门限方案

秘密共享的思想是将秘密以适当的方式拆分，拆分后的每一个份额由不同的参与者管理，单个参与者无法恢复秘密信息，只有若干个参与者一同协作才能恢复秘密消息。更重要的是，当其中任何相应范围内参与者出问题时，秘密仍可以完整恢复。

秘密共享是一种将秘密分割存储的密码技术，目的是阻止秘密过于集中，以达到分散风险和容忍入侵的目的，是信息安全和数据保密中的重要手段

？[AFCTF2018]花开藏宝地【bloom方案】

https://webencrypt.org/secretsharing/#bloom

http://www.matrix67.com/blog/archives/1261

a1 =100459779913520540098065407420629954816677926423356769524759072632219106155849450125185205557491138357760494272691949199099803239098119602186117878931534968435982565071570831032814288620974807498206233914826253433847572703407678712965098320122549759579566316372220959610814573945698083909575005303253205653244238542300266460559790606278310650849881421791081944960157781855164700773081375247
d1 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820820091
a2 =305345133911395218573790903508296238659147802274031796643017539011648802808763162902335644195648525375518941848430114497150082025133000033835083076541927530829557051524161069423494451667848236452337271862085346869364976989047180532167560796470067549915390773271207901537847213882479997325575278672917648417868759077150999044891099206133296336190476413164240995177077671480352739572539631359
d2 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820813413
a3 = 152012681270682340051690627924586232702552460810030322267827401771304907469802591861912921281833890613186317787813611372838066924894691892444503039545946728621696590087591246339208248647926966446848123290344911662916758039134817404720512465817867255277476717353439505243247568126193361558042940352204093381260402400739429050280526212446967632582771424597203000629197487733610187359662268583
d3 =347051559622463144539669950096658163425646411435797691973701513725701575100810446175849424000000075855070430240507732735393411493866540572679626172742301366146501862670272443070970511943485865887494229487420503750457974262802053722093905126235340380261828593508455621667309946361705530667957484731929151875527489478449361198648310684702574627199321092927111137398333029697068474762820818553

dd = d1*d2*d3
t1 = pow(dd//d1,d1-2,d1)
assert(t1*d2*d3%d1 == 1)
t2 = pow(dd//d2,d2-2,d2)
assert(t2*d1*d3%d2 == 1)
t3 = pow(dd//d3,d3-2,d3)
assert(t3*d2*d1%d3 == 1)
s = a1*t1*d2*d3+a2*t2*d1*d3+a3*t3*d1*d2
p = 80804238007977405688648566160504278593148666302626415149704905628622876270862865768337953835725801963142685182510812938072115996355782396318303927020705623120652014080032809421180400984242061592520733710243483947230962631945045134540159517488288781666622635328316972979183761952842010806304748313326215619695085380586052550443025074501971925005072999275628549710915357400946408857
s %= dd
# print(hex(s))
s %= p
s = hex(s)[2:]
flag = list(bytearray.fromhex(s))
for i in flag:
    print(chr(i),end="")

RSA

[HDCTF2019]together 【多文件共模攻击】

先分别分析两个公钥文件

with open("pubkey2.pem",'rb') as f:
    pub = RSA.importKey(f.read())
    n = pub.n
    e = pub.e
    print(n,'\n',e)

发现n相同，e不同。可以利用共模攻击。读取myflag文件后需要base64解码

e1 = 2333
e2 = 23333
n = 14853081277902411240991719582265437298941606850989432655928075747449227799832389574251190347654658701773951599098366248661597113015221566041305501996451638624389417055956926238595947885740084994809382932733556986107653499144588614105694518150594105711438983069306254763078820574239989253573144558449346681620784979079971559976102366527270867527423001083169127402157598183442923364480383742653117285643026319914244072975557200353546060352744263637867557162046429886176035616570590229646013789737629785488326501654202429466891022723268768841320111152381619260637023031430545168618446134188815113100443559425057634959299
with open('myflag1','rb') as f:
    c1 = base64.b64decode(f.read())
    print(c1)
with open('myflag2','rb') as f:
    c2 = base64.b64decode(f.read())
    print(c2)
gcd,s,t = gmpy2.gcdext(e1,e2)
c1 = libnum.s2n(c1)
c2 = libnum.s2n(c2)
if s < 0:
    s = -s
    c1 = gmpy2.invert(c1,n)
if t < 0:
    t = -t
    c2 = gmpy2.invert(c2,n)

M = gmpy2.powmod(c1,s,n)*gmpy2.powmod(c2,t,n) % n
m = hex(M)
print(m)
print(codecs.decode(m[2:],'hex'))
m = m[2:]
missing_padding = 4 - len(m) % 4
if missing_padding:
    m += '=' * missing_padding
print(base64.b64decode(m))

[MRCTF2020]babyRSA 【数学计算】

看脚本

过程都是和rsa一样，因此得到p，q即可正常解密

生成p的方式中间有的和rsa类似，因此类比，phi为(P[i]-1)乘积

P = [0 for i in range(17)]
P[9] = 206027926847308612719677572554991143421
n = 206027926847308612719677572554991143421
phi = 206027926847308612719677572554991143420
c = 213671742765908980787116579976289600595864704574134469173111790965233629909513884704158446946409910475727584342641848597858942209151114627306286393390259700239698869487469080881267182803062488043469138252786381822646126962323295676431679988602406971858136496624861228526070581338082202663895710929460596143281673761666804565161435963957655012011051936180536581488499059517946308650135300428672486819645279969693519039407892941672784362868653243632727928279698588177694171797254644864554162848696210763681197279758130811723700154618280764123396312330032986093579531909363210692564988076206283296967165522152288770019720928264542910922693728918198338839
for i in range(10,17):
    P[i] = sympy.nextprime(P[i-1])
    print(i, P[i])
    n*= P[i]
    phi *= P[i]-1
for i in range(8,0,-1):
    P[i] = sympy.prevprime(P[i+1])
    print(i,P[i])
    n *= P[i]
    phi *= P[i]-1
print(n)
e = 65537
d = gmpy2.invert(e,phi)
p = pow(c,d,n)
print(p)
print(sympy.nextprime(p))

q直接根据计算即可

q = pow(sub_q,q2,q1)

[De1CTF2019]babyrsa 【综合】

依次分析所需要的参数

根据中国剩余定理求得p^4，开四次方求得p为

from sympy.ntheory.modular import crt
m = [
    20129615352491765499340112943188317180548761597861300847305827141510465619670536844634558246439230371658836928103063432870245707180355907194284861510906071265352409579441048101084995923962148527097370705452070577098780246282820065573711015664291991372085157016901209114191068574208680397710042842835940428451949500607613634682684113208766694028789275748528254287705759528498986306494267817198340658241873024800336013946294891687591013414935237821291805123285905335762719823771647853378892868896078424572232934360940672962436849523915563328779942134504499568866135266628078485232098208237036724121481835035731201383423,
    31221650155627849964466413749414700613823841060149524451234901677160009099014018926581094879840097248543411980533066831976617023676225625067854003317018794041723612556008471579060428898117790587991055681380408263382761841625714415879087478072771968160384909919958010983669368360788505288855946124159513118847747998656422521414980295212646675850690937883764000571667574381419144372824211798018586804674824564606122592483286575800685232128273820087791811663878057827386379787882962763290066072231248814920468264741654086011072638211075445447843691049847262485759393290853117072868406861840793895816215956869523289231421,
    29944537515397953361520922774124192605524711306753835303703478890414163510777460559798334313021216389356251874917792007638299225821018849648520673813786772452822809546571129816310207232883239771324122884804993418958309460009406342872173189008449237959577469114158991202433476710581356243815713762802478454390273808377430685157110095496727966308001254107517967559384019734279861840997239176254236069001453544559786063915970071130087811123912044312219535513880663913831358790376650439083660611831156205113873793106880255882114422025746986403355066996567909581710647746463994280444700922867397754748628425967488232530303,
    25703437855600135215185778453583925446912731661604054184163883272265503323016295700357253105301146726667897497435532579974951478354570415554221401778536104737296154316056314039449116386494323668483749833147800557403368489542273169489080222009368903993658498263905567516798684211462607069796613434661148186901892016282065916190920443378756167250809872483501712225782004396969996983057423942607174314132598421269169722518224478248836881076484639837343079324636997145199835034833367743079935361276149990997875905313642775214486046381368619638551892292787783137622261433528915269333426768947358552919740901860982679180791]
r = [
    19131432661217908470262338421299691998526157790583544156741981238822158563988520225986915234570037383888112724408392918113942721994125505014727545946133307329781747600302829588248042922635714391033431930411180545085316438084317927348705241927570432757892985091396044950085462429575440060652967253845041398399648442340042970814415571904057667028157512971079384601724816308078631844480110201787343583073815186771790477712040051157180318804422120472007636722063989315320863580631330647116993819777750684150950416298085261478841177681677867236865666207391847046483954029213495373613490690687473081930148461830425717614569,
    15341898433226638235160072029875733826956799982958107910250055958334922460202554924743144122170018355117452459472017133614642242411479849369061482860570279863692425621526056862808425135267608544855833358314071200687340442512856575278712986641573012456729402660597339609443771145347181268285050728925993518704899005416187250003304581230701444705157412790787027926810710998646191467130550713600765898234392350153965811595060656753711278308005193370936296124790772689433773414703645703910742193898471800081321469055211709339846392500706523670145259024267858368216902176489814789679472227343363035428541915118378163012031,
    18715065071648040017967211297231106538139985087685358555650567057715550586464814763683688299037897182845007578571401359061213777645114414642903077003568155508465819628553747173244235936586812445440095450755154357646737087071605811984163416590278352605433362327949048243722556262979909488202442530307505819371594747936223835233586945423522256938701002370646382097846105014981763307729234675737702252155130837154876831885888669150418885088089324534892506199724486783446267336789872782137895552509353583305880144947714110009893134162185382309992604435664777436197587312317224862723813510974493087450281755452428746194446,
    2282284561224858293138480447463319262474918847630148770112472703128549032592187797289965592615199709857879008271766433462032328498580340968871260189669707518557157836592424973257334362931639831072584824103123486522582531666152363874396482744561758133655406410364442174983227005501860927820871260711861008830120617056883514525798709601744088135999465598338635794275123149165498933580159945032363880613524921913023341209439657145962332213468573402863796920571812418200814817086234262280338221161622789516829363805084715652121739036183264026120868756523770196284142271849879003202190966150390061195469351716819539183797]

a = crt(m,r)
print(a[0])
print(gmpy2.mpz(pow(a[0],1/4)))

109935857933867829728985398563235455481120300859311421762540858762721955038310117609456763338082237907005937380873151279351831600225270995344096532750271070807051984097524900957809427861441436796934012393707770012556604479065826879107677002380580866325868240270494148512743861326447181476633546419262340100453

可以根据小公钥指数加密（m^e<n 相对而言）

解出e2=381791429275130

e1 = 15218928658178

分解n

q1p即q1为127587319253436643569312142058559706815497211661083866592534217079310497260365307426095661281103710042392775453866174657404985539066741684196020137840472950102380232067786400322600902938984916355631714439668326671310160916766472897536055371474076089779472372913037040153356437528808922911484049460342088834871

得到hint为

orz…you.found.me.but.sorry.no.hint…keep.on.and.enjoy.it!

最后，根据给出的条件看，一般情况用一个式子即可求解，但是报错无法求逆元d。发现gcd(e1,(p-1)(q1-1))=14。因此需要进行变形

$$c1=m^{e1}\ mod\ (p*q1)=(m^{14})^{e1\div14}\mod\ (p*q1)$$

可以在此条件下求出m14 的通解(显然最小特解很大可能不是答案,因为这个解还需要满足第二个方程)

第二个方程同理，用中国剩余定理求得m^14

将同余方程组进行细化

m^14 ☰a1 mod p
m^14 ☰ a1 mod q1
m^14 ☰ a2 mod p
m^14 ☰ a2 mod q2

由于m的指数过大,我们尝试通过构造一个新的rsa式子来降解m的指数.理论上4个方程有6种合并方式.但是通过计算gcd(p-1,7)!=1所以如果选择p的话显然是行不通的.于是舍弃p,选择q1,q2进行合并.得到一个全新的方程以后再通过一般求解rsa的方法就可以了

m^14 = (m^2)^7 mod (q1*q2)

看作新的rsa，e为7，c为之前求得m^14，最后求得m^2，再分解即可

[NPUCTF2020]认清形势，建立信心【选择明文攻击】

[NPUCTF2020]共模攻击 【coppersmith]

Coppersmith定理的内容为：在一个e阶的mod n多项式f(x)中，如果有一个根小于n^1/e，就可以运用一个O(log n)的算法求出这些根

task中我们可以获取的信息有：

$$c1 = m^p\ mod\ n = m^p\ mod \ p*q$$

$$c2 = m^q\ mod\ n = m^q\ mod\ p*q$$

因为p、q为素数，所以由费马定理可得：

$$m^p ≡ m\ mod\ p$$

$$m^q ≡ m\ mod\ q$$

所以，又有：

c1 = m + ip + xpq，可整理成 c1 = m + ip

c2 = m + jq + ypq，可整理成 c2 = m + jq

因此：

c1 * c2 = m2 + (ip + jq)m + ijn

(c1 + c2)m = 2m2 + (ip+jq)m

有： m2 - (c1 + c2)m + c1 * c2 = ijn ≡ 0 mod n

最终的任务就是求m的值。

n=128205304743751985889679351195836799434324346996129753896234917982647254577214018524580290192396070591032007818847697193260130051396080104704981594190602854241936777324431673564677900773992273463534717009587530152480725448774018550562603894883079711995434332008363470321069097619786793617099517770260029108149
c1=96860654235275202217368130195089839608037558388884522737500611121271571335123981588807994043800468529002147570655597610639680977780779494880330669466389788497046710319213376228391138021976388925171307760030058456934898771589435836261317283743951614505136840364638706914424433566782044926111639955612412134198
c2=9566853166416448316408476072940703716510748416699965603380497338943730666656667456274146023583837768495637484138572090891246105018219222267465595710692705776272469703739932909158740030049375350999465338363044226512016686534246611049299981674236577960786526527933966681954486377462298197949323271904405241585

PR.<m> = PolynomialRing(Zmod(n))
#Zmod(n):指定模，定义界限为n的环；Z表示整数；指定模是划定这个环的界限，就是有效的数字只有从0到n，其他的都通过与n取模来保证在0～n这个范围内；Zmod代表这是一个整数域中的n模环
#ZZ：整数环；QQ：有理数环；RR：实数环；CC：复数环
#PR：只是一个指针，指向用polynomialring指定的那个环（可以使用任意字符）
#PolynomialRing：这个就是说建立多项式环
#.<m>：指定一个变量的意思（可以用任意字符）
f = m^2-(c1+c2)*m+c1*c2
x0 = f.small_roots(X=2^400)
#x的绝对边界，因为m<400bits，所以设为2^400
print(x0)

https://xz.aliyun.com/t/6813

coppersmith攻击总结https://www.ruanx.net/coppersmith/

[QCTF2018]Xman-RSA

查看encryption.encrypted，看代码应该是作了一个简单的替换加密，使用quipquip进行频率分析，还原出代码（其中大写的T没有作替换）

from gmpy2 import is_prime 
from os import urandom 
import base64 
def bytes_to_num(b): 
	return int(b.encode('hex'), 16) 

def num_to_bytes(n): 
	b = hex(n)[2:-1] 
	b = '0' + b if len(b)%2 == 1 else b 
	return b.decode('hex') 

def get_a_prime(l): 
	random_seed = urandom(l) 
	num = bytes_to_num(random_seed) 
	while True: 
		if is_prime(num): 
			break 
		num+=1 
	return num 

def encrypt(s, e, n): 
	p = bytes_to_num(s) 
	p = pow(p, e, n) 
	return num_to_bytes(p).encode('hex') 

def separate(n): 
	p = n % 4 
	t = (p*p) % 4 
	return t == 1 

f = open('flag.txt', 'r') 
flag = f.read() 

msg1 = "" 
msg2 = "" 
for i in range(len(flag)): 
	if separate(i): 
		msg2 += flag[i] 
	else: 
		msg1 += flag[i]

p1 = get_a_prime(128) 
p2 = get_a_prime(128) 
p3 = get_a_prime(128) 
n1 = p1*p2 
n2 = p1*p3 
e = 0x1001 
c1 = encrypt(msg1, e, n1) 
c2 = encrypt(msg2, e, n2) 
print(c1) 
print(c2) 
e1 = 0x1001 
e2 = 0x101 
p4 = get_a_prime(128) 
p5 = get_a_prime(128) 
n3 = p4*p5 
c1 = num_to_bytes(pow(n1, e1, n3)).encode('hex') 
c2 = num_to_bytes(pow(n1, e2, n3)).encode('hex') 
print(c1) 
print(c2) 
print(base64.b64encode(num_to_bytes(n2))) 
print(base64.b64encode(num_to_bytes(n3)))

进一步分析文件，n1中的应该是59、60行中的c1、c2，ciphertext是上面真正和flag有关的的c1、c2，最后是n2和n3

先求得n2和n3的值

n2 = "PVNHb2BfGAnmxLrbKhgsYXRwWIL9eOj6K0s3I0slKHCTXTAUtZh3T0r+RoSlhpO3+77AY8P7WETYz2Jzuv5FV/mMODoFrM5fMyQsNt90VynR6J3Jv+fnPJPsm2hJ1Fqt7EKaVRwCbt6a4BdcRoHJsYN/+eh7k/X+FL5XM7viyvQxyFawQrhSV79FIoX6xfjtGW+uAeVF7DScRcl49dlwODhFD7SeLqzoYDJPIQS+VSb3YtvrDgdV+EhuS1bfWvkkXRijlJEpLrgWYmMdfsYX8u/+Ylf5xcBGn3hv1YhQrBCg77AHuUF2w/gJ/ADHFiMcH3ux3nqOsuwnbGSr7jA6Cw=="
n3 = "TmNVbWUhCXR1od3gBpM+HGMKK/4ErfIKITxomQ/QmNCZlzmmsNyPXQBiMEeUB8udO7lWjQTYGjD6k21xjThHTNDG4z6C2cNNPz73VIaNTGz0hrh6CmqDowFbyrk+rv53QSkVKPa8EZnFKwGz9B3zXimm1D+01cov7V/ZDfrHrEjsDkgK4ZlrQxPpZAPl+yqGlRK8soBKhY/PF3/GjbquRYeYKbagpUmWOhLnF4/+DP33ve/EpaSAPirZXzf8hyatL4/5tAZ0uNq9W6T4GoMG+N7aS2GeyUA2sLJMHymW4cFK5l5kUvjslRdXOHTmz5eHxqIV6TmSBQRgovUijlNamQ=="
n2 = bytes_to_long(base64.b64decode(n2))
n3 = bytes_to_long(base64.b64decode(n3))
print(n2)
print(n3)

然后共模攻击，求得n1的值

c1 = "2639c28e3609a4a8c953cca9c326e8e062756305ae8aee6efcd346458aade3ee8c2106ab9dfe5f470804f366af738aa493fd2dc26cb249a922e121287f3eddec0ed8dea89747dc57aed7cd2089d75c23a69bf601f490a64f73f6a583081ae3a7ed52238c13a95d3322065adba9053ee5b12f1de1873dbad9fbf4a50a2f58088df0fddfe2ed8ca1118c81268c8c0fd5572494276f4e48b5eb424f116e6f5e9d66da1b6b3a8f102539b690c1636e82906a46f3c5434d5b04ed7938861f8d453908970eccef07bf13f723d6fdd26a61be8b9462d0ddfbedc91886df194ea022e56c1780aa6c76b9f1c7d5ea743dc75cec3c805324e90ea577fa396a1effdafa3090"
c2 = "42ff1157363d9cd10da64eb4382b6457ebb740dbef40ade9b24a174d0145adaa0115d86aa2fc2a41257f2b62486eaebb655925dac78dd8d13ab405aef5b8b8f9830094c712193500db49fb801e1368c73f88f6d8533c99c8e7259f8b9d1c926c47215ed327114f235ba8c873af7a0052aa2d32c52880db55c5615e5a1793b690c37efdd5e503f717bb8de716303e4d6c4116f62d81be852c5d36ef282a958d8c82cf3b458dcc8191dcc7b490f227d1562b1d57fbcf7bf4b78a5d90cd385fd79c8ca4688e7d62b3204aeaf9692ba4d4e44875eaa63642775846434f9ce51d138ca702d907849823b1e86896e4ea6223f93fae68b026cfe5fa5a665569a9e3948a"
c1 = codecs.decode(c1,'hex')
c1 = bytes_to_long(c1)
c2 = bytes_to_long(codecs.decode(c2,'hex'))
e1 = 0x1001
e2 = 0x101
n = n3
gcd,s,t = gmpy2.gcdext(e1,e2)
if s < 0:
    s = -s
    c1 = gmpy2.invert(c1,n)
if t < 0:
    t = -t
    c2 = gmpy2.invert(c2,n)

M = gmpy2.powmod(c1,s,n)*gmpy2.powmod(c2,t,n) % n
print(M)
n1 = M

最后求解得到msg1，msg2。再分析separate函数，发现只是交错分割flag

所以还原即可。

注意字节码需要decode()转换为字符串。

给到的函数num_to_bytes不知道为什么可能有一点小问题，最后需要改用long_to_bytes

p = gmpy2.gcd(n1,n2)


def decrypt(c,e,n):
    c = bytes_to_num(codecs.decode(c,'hex'))
    q = divmod(n,p)[0]
    phi_n = (p-1)*(q-1)
    d = gmpy2.invert(e,phi_n)
    m = pow(c,d,n)

    return long_to_bytes(m)


c1 = "1240198b148089290e375b999569f0d53c32d356b2e95f5acee070f016b3bef243d0b5e46d9ad7aa7dfe2f21bda920d0ac7ce7b1e48f22b2de410c6f391ce7c4347c65ffc9704ecb3068005e9f35cbbb7b27e0f7a18f4f42ae572d77aaa3ee189418d6a07bab7d93beaa365c98349d8599eb68d21313795f380f05f5b3dfdc6272635ede1f83d308c0fdb2baf444b9ee138132d0d532c3c7e60efb25b9bf9cb62dba9833aa3706344229bd6045f0877661a073b6deef2763452d0ad7ab3404ba494b93fd6dfdf4c28e4fe83a72884a99ddf15ca030ace978f2da87b79b4f504f1d15b5b96c654f6cd5179b72ed5f84d3a16a8f0d5bf6774e7fd98d27bf3c9839"
c2 = "129d5d4ab3f9e8017d4e6761702467bbeb1b884b6c4f8ff397d078a8c41186a3d52977fa2307d5b6a0ad01fedfc3ba7b70f776ba3790a43444fb954e5afd64b1a3abeb6507cf70a5eb44678a886adf81cb4848a35afb4db7cd7818f566c7e6e2911f5ababdbdd2d4ff9825827e58d48d5466e021a64599b3e867840c07e29582961f81643df07f678a61a9f9027ebd34094e272dfbdc4619fa0ac60f0189af785df77e7ec784e086cf692a7bf7113a7fb8446a65efa8b431c6f72c14bcfa49c9b491fb1d87f2570059e0f13166a85bb555b40549f45f04bc5dbd09d8b858a5382be6497d88197ffb86381085756365bd757ec3cdfa8a77ba1728ec2de596c5ab"
e = 0x1001
msg1 = decrypt(c1,e,n1).decode()
msg2 = decrypt(c2,e,n2).decode()

print()

flag = ""
len = len(msg2) + len(msg1)
tmp1 = 0
tmp2 = 0
for i in range(len//2):
    flag += str(msg1[tmp1])
    flag += str(msg2[tmp2])
    tmp1+=1
    tmp2+=1

print(flag)

[羊城杯 2020]RRRRRRRSA 【wiener attack】

wiener attack：依靠连分数进行攻击，适用于非常接近某一值（如1）时，求一个比例关系，通过该比例关系再反推关键信息。

适用于解密指数d很小，满足以下条件

$$d < 1/3\ * N^{1/4} \\ q < p < 2q$$

一般用法：根据

$$ed\ mod\ phi(n) = 1$$

得到

$$e*d = 1 + k*phi(n) \\ 即\ e/phi(n) = k/d + 1/d*phi(n) \\ 而\ phi(n)接近于n \\ e/n - k/d = 1/d*phi(n) \\ e/n 与 k/d非常接近 \\$$

而e/N又是已知的,因此对e/N进行连分数展开，得到的一串分数的分母很有可能就是d，只要检验一下 ed mod phi(n) 看它是不是1就知道对不对了。

本题特殊之处：e与N并没有近到相除约为1的地步，相差还是很大的，也就是说解密指数d也许还是很大的，这样就解不出来。但是N1和N2的关系却适合。

$$N1/N2=(p1/p2)^2\ * (q1/q2)$$

显然我们可以知道的是N1/N2 <Q1/Q2，所以在Q1/Q2在区间(N1/N2,1)之间，尝试对N1/N2进行连分数展开并求其各项渐进分数，其中某个连分数的分母可能就是Q1（这个可以依靠N%Q来验证）

N1 =
N2 =
#求连分数的项
def continuedfra(x,y):
    cf = []
    while y:
        cf += [x//y]
        x,y = y,x%y
    return cf
#得到分子和分母
def simplify(c):
    numrator = 0 #分子
    denominator = 1 #分母
    for x in c[::-1]: #倒序遍历？
        numrator,denominator = denominator,x * denominator + numrator
    return (numrator,denominator) #连分数生成分子和算出来的分母？

def getit(c):
    cf = []
    for i in range(len(c)):
        cf.append(simplify(c[:i]))
    return cf

def wiener(e,n):
    cf = []
    for (Q2,Q1) in getit(cf):
        if Q1 == 0:
            continue
        if N1%Q1 == 0 and Q1 != 1:
            return Q1
    print("not found")
    return 0
Q1 = wiener(N1,N2)

！[watevrCTF 2019]Swedish RSA【多项式】

https://blog.csdn.net/MikeCoke/article/details/113800879

多项式的欧拉函数：对于多项式P(y)来讲，欧拉函数phi(P(y))表示所有不高于P(y)幂级的环内所有多项式中，与P(y)无（除1以外）公因式的其他多项式的个数。

[美团CTF]hambersa 【PP】

x, y = len(str§), len(str(q))
P = 10^x * p + p
Q = 10^y * q + q
同理
PP = 10^x’ * P + Q
QQ = 10^y’ * Q + P

N = 10^(x+x’+y+y’)pq+…+pq

sage代码

from Crypto.Util.number import *
from tqdm import tqdm

def decrypt_RSA(c, e, p, q):
    phi = (p-1) * (q-1)
    d = inverse(e, phi)
    m = pow(c, d, p*q)
    print(long_to_bytes(m))

n = 177269125756508652546242326065138402971542751112423326033880862868822164234452280738170245589798474033047460920552550018968571267978283756742722231922451193
c = 47718022601324543399078395957095083753201631332808949406927091589044837556469300807728484035581447960954603540348152501053100067139486887367207461593404096


low = str(n)[-18:]
high = str(n)[:18]
pq_prob = []

for i in range(10):
    for j in range(10):
        for k in range(10):
            pq_prob.append(int(high + str(i) + str(j)+ str(k) + low))

for x in tqdm(pq_prob):
    f = factor(x)
    if (len(f) == 2 and f[0][0].nbits() == 64):
        p, q = f[0][0], f[1][0]
        break

P = int(str(p) + str(p))
print(P)
Q = int(str(q) + str(q))
PP = int(str(P) + str(Q))
QQ = int(str(Q) + str(P))
N = PP * QQ
print(N == n)
decrypt_RSA(c, 65537, PP, QQ)```

[NCTF2019]easyrsa【e，phi不互素】

http://yulige.top/?p=752#easyRSA909pt_2solvers

然而本题则为e和p-1(或q-1)的最大公约数就是e本身，也就是说e | p-1，只有对c开e次方根才行，但是e很大，暴力计算所需时间很长。
可以将同余方程

$$m^e \equiv c \quad (\text{mod}\ n)$$

$$化成\\ \begin{aligned} m^e &\equiv c \quad (\text{mod}\ p)\newline m^e &\equiv c \quad (\text{mod}\ q) \end{aligned}$$

然后分别在GF(p)和GF(q)上对c开e=0x1337次方根，再用CRT组合一下即可得到在mod n下的解

**有限域内开根： **

e与p-1和q-1都不互素，不能简单求个逆元

开平方根可以用 Tonelli-Shanks算法，可以扩展到开n次方根

这篇paper 里给出了具体的算法：Adleman-Manders-Miller rth Root Extraction Method

数学证明以后再看吧2333

def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - discrete_log(d, a)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

但该算法只能求得一个根，实际上开0x1337次方，最多会有0x1337个根。

那么如何找到其他根呢？

先找到所有0x1336个proot使得

$$proot^e = 1 (mod\ p)$$

然后乘以上面求得的根即可。

由于

$$(proot^{p-1/e})^e = proot^{p-1} = 1 (mod\ p)$$

所以只需要

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        g = pow(random.randint(2, p-1), (p-1)//e, p)
        if pow(g,e//2,p) != 1:
            proot.add(g)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

完整sage代码如下

[百度2021]time【p，q相近+随机数遍历】

首先看到q是p的下一个素数，可以发现p，q非常相近，所以

$$|p-q|很小\\ （p+q)/2 与 \sqrt[2]{n}很接近\\ 从\sqrt[2]{n}开始直到找到一个x，使得x^2-n=y^2即可\\ p = x-y \\ q = x + y$$

pp = gmpy2.iroot(n,2)[0]
for x in range(pp+1,pp+3):
    yy = pow(x,2)-n
    if gmpy2.iroot(yy,2)[1]:
        y = gmpy2.iroot(yy,2)[0]
        p = (x-y)
        q = x + y
        print("p:",p)
        print("q:",q)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)
print(m)
print(long_to_bytes(m))

得到hint

localtime为time.struct_time(tm_year=2021, tm_mon=4, tm_mday=28, tm_hour=20, tm_min=42, tm_sec=6, tm_wday=2, tm_yday=118, tm_isdst=0)

time()-a1 = 3.1603143215179443

randome.seed设置的种子相同的话，最后得到的随机数也相同，所以只需要进行遍历即可

lt = time.mktime((2021,4,28,20,42,6,2,118,0))
print(lt)
a1 = 3.1603143215179443
s = 0
for i in range(3):
    for j in range(100000):
        random.seed(s)
        x = random.getrandbits(2048)
        s = int(lt) - i + j * 10 ** -5
        if n % x == 0:
            p = x
            print(p)
            q = n//p
            phi = (p-1)*(q-1)
            d = gmpy2.invert(e,phi)
            m = pow(c,d,n)
            print(long_to_bytes(m))
            break
        

[百度ichunqiu]whitegiveCMA【数论+共模】

[GKCTF2021]RRRsa【数学式子化简】

1）拿到两个式子后，先把括号去掉，然后把常数项去掉；
2）之后得到的式子应该是俩个只含p或q的式子，让两个式子的p（或q）的指数和系数相同；
3）将两个式子相加或相减消掉p,剩下的式子应该只剩下q,与n进行gcd（）求出q

import gmpy2
import Rsa
t= 202020*212121
h3=25590923416756813543880554963887576960707333607377889401033718419301278802157204881039116350321872162118977797069089653428121479486603744700519830597186045931412652681572060953439655868476311798368015878628002547540835719870081007505735499581449077950263721606955524302365518362434928190394924399683131242077
h4=104100726926923869566862741238876132366916970864374562947844669556403268955625670105641264367038885706425427864941392601593437305258297198111819227915453081797889565662276003122901139755153002219126366611021736066016741562232998047253335141676203376521742965365133597943669838076210444485458296240951668402513
n2 = 114535923043375970380117920548097404729043079895540320742847840364455024050473125998926311644172960176471193602850427607899191810616953021324742137492746159921284982146320175356395325890407704697018412456350862990849606200323084717352630282539156670636025924425865741196506478163922312894384285889848355244489
h = pow(2021,t,n2)*pow(h3,212121,n2)-pow(2020,t,n2)*pow(h4,202020,n2)
q2 = gmpy2.gcd(n2,h)
print(q2)
p2 = n2//q2
print(p2)
c2 = 67054203666901691181215262587447180910225473339143260100831118313521471029889304176235434129632237116993910316978096018724911531011857469325115308802162172965564951703583450817489247675458024801774590728726471567407812572210421642171456850352167810755440990035255967091145950569246426544351461548548423025004
d = Rsa.get_d(65537,p2,q2,n2)
q = Rsa.decrypt(c2,d,n2)

n1=75003557379080252219517825998990183226659117019770735080523409561757225883651040882547519748107588719498261922816865626714101556207649929655822889945870341168644508079317582220034374613066751916750036253423990673764234066999306874078424803774652754587494762629397701664706287999727238636073466137405374927829
c1=68111901092027813007099627893896838517426971082877204047110404787823279211508183783468891474661365139933325981191524511345219830693064573462115529345012970089065201176142417462299650761299758078141504126185921304526414911455395289228444974516503526507906721378965227166653195076209418852399008741560796631569
hint1=23552090716381769484990784116875558895715552896983313406764042416318710076256166472426553520240265023978449945974218435787929202289208329156594838420190890104226497263852461928474756025539394996288951828172126419569993301524866753797584032740426259804002564701319538183190684075289055345581960776903740881951
hint2=52723229698530767897979433914470831153268827008372307239630387100752226850798023362444499211944996778363894528759290565718266340188582253307004810850030833752132728256929572703630431232622151200855160886614350000115704689605102500273815157636476901150408355565958834764444192860513855376978491299658773170270
q1 = gmpy2.gcd(n1,pow(hint2-212121,202020,n1)*pow(2020,202020,n1)-hint1*pow(2021,202020,n1))
print(q1)
p1 = n1//q1
d = Rsa.get_d(65537,p1,q1,n1)
p = Rsa.decrypt(c1,d,n1)

c = 13492392717469817866883431475453770951837476241371989714683737558395769731416522300851917887957945766132864151382877462142018129852703437240533684604508379950293643294877725773675505912622208813435625177696614781601216465807569201380151669942605208425645258372134465547452376467465833013387018542999562042758
d = Rsa.get_d(65537,p,q,p*q)
m = Rsa.decrypt(c,d,p*q)

ELgamal

Hash

脑洞