Crypto系列——RSA（三）

[RSA3]P1

main

from Crypto.Util.number import *
flag = b'******'

m1 = bytes_to_long(flag[:len(flag)//2])
m2 = bytes_to_long(flag[len(flag)//2:])

assert 18608629446895353521310408885845687520013234781800558*m1-14258810472138345414555137649316815272478951117940067*m2 == 1

exp

本题非常直白，将flag分成两部分后给了一个约束式，让我们求解flag。

约束是一个二元一次方程，显然我们知道二元一次方程在实数域上会有无数个解，但注意我们很少会在实数域上进行运算，我们所有的操作都是在一个整数域或者有限域（可以理解为取模的域）中进行运算。而这里我们便有一个非常常用的裴蜀定理

裴蜀定理：对于整数域中的不定方程\(ax+by=m\)，其有解的充要条件为\(gcd(a,b)\ | \ m\)

裴蜀定理，又称贝祖定理。是一个关于最大公约数的定理。其内容定义为：对于不全为零的任意整数 a 和 b，记二者的最大公约数为 g 即 gcd(a,b) = g，则对于任意整数 x 和 y 都一定满足 ax+by 是 g 的倍数。

特别地，一定存在整数 x 和 y 的解，使得 \(ax+by=gcd(a,b)\) 成立。

它的一个重要推论为：a,b互质的充分必要条件是存在整数x,y 使 ax+by=1; 或者说对于方程 ax+by=1 只有整数a和b互质时，方程才有整数解x,y。

import gmpy2
from Crypto.Util.number import long_to_bytes
 
a = 18608629446895353521310408885845687520013234781800558
b = 14258810472138345414555137649316815272478951117940067
g, m1, m2 = gmpy2.gcdext(a, b)
# gcdext 函数,该函数计算两个整数的最大公约数，并返回扩展欧几里得算法的解。
#g 是最大公约数。m1 和 m2 是扩展欧几里得算法的解，满足方程 a * m1 + b * m2 = g。
# print(m1,m2)
 
for i in range(10):
    mh = long_to_bytes(m1 + i*b)
    if b'NSSCTF' in mh:
        ml = long_to_bytes(-m2 + i*a)
        print(mh + ml)
        break

至于算完m1和m2为什么还有下面的部分：

for i in range(10):
    mh = long_to_bytes(m1 + i*b)
    if b'NSSCTF' in mh:
        ml = long_to_bytes(-m2 + i*a)
        print(mh + ml)
        break

这简直是一头🐖都能想到问题了吖（说的是博主本人是🐖

当然是因为\(a(m1 + i*b)+b(-m2 + i*a)=g\)，

那为什么是\(-m_2\)呢

因为\(m_2\)是一个负数，你写\(m_2\)会报错，写成\(-m_2\)就好了

浅谈扩展欧几里得算法-CSDN博客

[RSA3]P2(高次Rabin)

main

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

flag = b'NSSCTF{******}'

p = getPrime(256)
q = getPrime(256)

assert p%4 == 3 and q%4 == 3

n = p*q
e = 4
m = bytes_to_long(flag)

c = powmod(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 59146104467364373868799971411233588834178779836823785905639649355194168174467
q = 78458230412463183024731868185916348923227701568297699614451375213784918571587
e = 4
c = 1203393285445255679455330581174083350744414151272999693874069337386260499408999133487149585390696161509841251500970131235102423165932460197848215104528310
'''

exp

高次Rabin，这里是两次，如果是16次把for i in range(2):中的2改成16即可

# 脚本喵，只会脚本了说是😭
from Crypto.Util.number import *
import gmpy2


p = 59146104467364373868799971411233588834178779836823785905639649355194168174467
q = 78458230412463183024731868185916348923227701568297699614451375213784918571587
e = 4
c = 1203393285445255679455330581174083350744414151272999693874069337386260499408999133487149585390696161509841251500970131235102423165932460197848215104528310

n = p*q

x0=gmpy2.invert(p,q)
x1=gmpy2.invert(q,p)
cs = [c]
for i in range(2):
    ps = []
    for c2 in cs:
        r = pow(c2, (p + 1) // 4, p)
        s = pow(c2, (q + 1) // 4, q)

        x = (r * x1 * q + s * x0 * p) % n
        y = (r * x1 * q - s * x0 * p) % n
        if x not in ps:
            ps.append(x)
        if n - x not in ps:
            ps.append(n - x)
        if y not in ps:
            ps.append(y)
        if n - y not in ps:
            ps.append(n - y)
    cs = ps

for m in ps:
    flag = long_to_bytes(m)
    if b"NSSCTF" in flag:
        print(flag)
        break

[RSA3]P3

main

exp

[RSA3]P4

main

exp

[RSA3]P5(CRT)

main

from Crypto.Util.number import *
from gmpy2 import *
import random
flag = b'******'
flag = bytes_to_long(flag)
nl = []
cl = []

def getn(bits):
    n = 1
    while n.bit_length() < bits:
        n *= random.choice(sieve_base)
    return n

for i in range(8):
    n = getn(flag.bit_length())
    c = pow(flag, 7, n)

    nl.append(n)
    cl.append(c)

print(nl)
print(cl)

'''
nl = [48900330639594979739701067783234903348599405413588466525574910520196852415104874636276388006189258357683981763, 52184798260918956005878710130354843122927544013692595240956998112200987084814453592388074200951779840156511, 57591305346419909943538345276263585821186563609432856462492112562586368230163591993342956384688555395772999, 1391052858660682537388264601016075339528373211889618359237336378385137832855656756800539626220549334300176727, 8401669052993451281764489325068020625937224410830694438332016050030698435746929661939302694116817188225591, 66809775375777747860816961274643428927028556487820183599747024350362932190079439298182707730302976119988715497, 41209230281867957743385705727577318625405890894626062454495908709761427062490881938652489884059847194603237277, 31140089821370202352241944402736292072447365626312703496944186462246895695650729682254970622208848300946861]
cl = [26617913696414745819584063604277199673357890677059949687794606743781436349829925794253672010780125661705587071, 6332739614121961923948917957498597962902897015582697635859365080803944882904908423983706426654363433337197, 46154051334276357655176765655327305918368830821288083739892570534253190653909520953027859629573215723954424, 2800905135165447908315158053695706832127646195243072751493365013371469263897970241141686022109978485359114, 3597083928897756955519089479028751799504001377334447013725903377254761160933418420625119547713455139382114, 17032086144873551648611964054579542303630306316746409528107026138674853298939194425805809444921339677455174485, 36111201824253386572496248461433786832561483450731317363761227351689971628309683994429845284904292821369745345, 28548175317543234723297895187238113463350377151401226415566179373530461612253257137535830491771909906093171]
'''

exp

[RSA3]P6

main

exp

[RSA3]P7

main

exp

[RSA3]P8

main

exp

[RSA3]P9

main

exp

[RSA3]P10

main

exp

[RSA3]P11

main

exp

[RSA3]P12

main

exp