13

[BUUCTF-crypto]writeup【loading】

 1 year ago
source link: https://scorpionre.github.io/2022/01/24/BUUCTF-crypto-writeup-md/#%E8%84%91%E6%B4%9E
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Scorpion

[BUUCTF-crypto]writeup【loading】

Created2022-01-24|Updated2022-01-25|cryptoctf
Word count:6.8k|Reading time:30min|Post View:54

[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（空格）异或；找出相应位置的密钥字节。

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

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

词频分析

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="")

[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

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=me1mod(p∗q1)=(m14)e1÷14mod(p∗q1)c1=m^{e1}\ mod\ (p*q1)=(m^{14})^{e1\div14}\mod\ (p*q1) c1=me1 mod (p∗q1)=(m14)e1÷14mod (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=mpmodn=mpmodp∗qc1 = m^p\ mod\ n = m^p\ mod \ p*q c1=mp mod n=mp mod p∗q
c2=mqmodn=mqmodp∗qc2 = m^q\ mod\ n = m^q\ mod\ p*q c2=mq mod n=mq mod p∗q

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

mp≡mmodpm^p ≡ m\ mod\ p mp≡m mod p
mq≡mmodqm^q ≡ m\ mod\ q mq≡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∗N1/4q<p<2qd < 1/3\ * N^{1/4} \\ q < p < 2q d<1/3 ∗N1/4q<p<2q

一般用法：根据

edmodphi(n)=1ed\ mod\ phi(n) = 1 ed mod phi(n)=1
e∗d=1+k∗phi(n) 即 e/phi(n)=k/d+1/d∗phi(n) 而 phi(n) 接近于 ne/n−k/d=1/d∗phi(n)e/n 与 k/d 非常接近 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∗d=1+k∗phi(n) 即 e/phi(n)=k/d+1/d∗phi(n) 而 phi(n) 接近于 ne/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=(p1/p2)^2\ * (q1/q2) 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 很大，暴力计算所需时间很长。
可以将同余方程

me≡c(mod n)m^e \equiv c \quad (\text{mod}\ n) me≡c(mod n)
化成 me≡c(mod p)me≡c(mod q) 化成 \\ \begin {aligned} m^e &\equiv c \quad (\text {mod}\ p)\newline m^e &\equiv c \quad (\text {mod}\ q) \end {aligned} 化成 meme​≡c(mod p)≡c(mod q)​

然后分别在 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 使得

proote=1(modp)proot^e = 1 (mod\ p) proote=1(mod p)

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

(prootp−1/e)e=prootp−1=1(modp)(proot^{p-1/e})^e = proot^{p-1} = 1 (mod\ p) (prootp−1/e)e=prootp−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 与 n2 很接近从 n2 开始直到找到一个 x，使得 x2−n=y2 即可 p=x−yq=x+y|p-q | 很小 \\ （p+q)/2 与 \sqrt [2]{n} 很接近 \\ 从 \sqrt [2]{n} 开始直到找到一个 x，使得 x^2-n=y^2 即可 \\ p = x-y \\ q = x + y ∣p−q∣很小（p+q)/2 与 2n​很接近从 2n​开始直到找到一个 x，使得 x2−n=y2 即可 p=x−yq=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


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK