两道CTF-RSA类题目总结

0x00 几句废话

可能是由于刚开学的原因,CTF线上赛不仅数量多,赛题质量也比较高.而且智能合约越来越成为比赛的宠儿,有空需要专门学习记录一下相关题目的做法及常见漏洞.

下面记录一下两道比较有意思的Crypto类RSA相关题目.

0x01 数学知识补充

Legendre symbol

勒让德符号(下文写成a|p)有如下定义:

legendre_symbol.png-52.3kB

基本性质

如果$ (a|p)=1 $,a便称为modp下的二次剩余;如果$ (a|p)=-1 $,则a称为mod p下的二次非剩余.通常把0视为一种特殊情况.
$(a|p) = +1/-1 \equiv a^{(p-1)/2} (mod p)$

其他性质

$(a\*b|p) = (a|p)\*(b|p)$
如果$ a \equiv b (mod p) $,则$ (a|p) = (b|p) $
$(a^2|p) = 1$
一般二次互反律

如果p和q是奇素数,则$ (q|p)=(p|q)(-1)^{(p-1)/2(q-1)/2} $
二次互反律的第一补充
二次互反律的第二补充

Jacobi symbol

雅可比符号是勒让德符号的推广,整数a对整数m的雅可比符号表示为(a|m).设m是大于1的奇数,且m的素因数分解式为$ m=p1*p2*p3….pr $(式中因数可以相同),如果(a,m)=1,则雅可比符号定义为:

(a|m) = (a|p1)(a|p2)(a|p3)...(a|pr)

其中(a|pi)是a对pi的勒让德符号符号.

0x02 Application of jacobi symbol

计算雅可比符号的python函数 `gmpy2.jacobi()`

题目来源

2019-9-6 N1ctf babyrsa

题目类型

Crypto,jacobi symbol,operator precedence

题目描述

该题目给出了加密脚本babyrsa.py以及加密之后的文件flag.enc.加密脚本如下:

#!/usr/bin/env python2
# -*- coding: utf-8 -*-
from Crypto.Util import number
import random
from secret import flag
N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
m = number.bytes_to_long(flag)
with open('flag.enc', 'w') as f:
    while m:
        padding = random.randint(0, 2**1000) ** 2
        message = padding << 1 + m % 2
        cipher = pow(message, e, N)
        f.write(hex(cipher)+'\n')
        m /= 2

题目分析

通过脚本我们可以看出大致的加密过程:首先将flag字符串转换成长整型数字.然后随机生成一定范围内的随机数并进行平方.由于运算符优先级问题,<<的优先级高于+,所以将处理后的随机数左移(1+flag[i])位.将移动后的结果进行rsa加密,结果以hex的形式存储在输出文件中.

分析算法之后,我们有两点需要注意,第一是运算符优先级问题,即左移的位数只能是1或2.第二是由于m%2的存在,加密的顺序是从flag的低位向高位进行,所以解密结果需要注意顺序.

下面来进行数学分析.经过上面的分析我们知道plain[i] = 2^(1+flag[i])*r^2显然当flag[i] == 1时,plain[i] = (2*r)^2(mod n)是一个二次剩余.如果flag[i] == 0时,plain[i]=2*r^2,此时2^(-1)*plain[i]=r^2 (mod n)是一个二次剩余.此类问题本质为模数域内的平方检测问题,于是联想到使用雅可比符号.

根据题目描述,我们可以得到cipher[i]=(2^(1+flag[i])*r^2)^e (mod n),根据性质计算雅可比符号:

7.png-70.3kB

由于$ N \equiv 5(mod 8) $,根据二次互反律可得$ (2|N) = -1 $,而且$ (1|N)=1 $.所以当雅可比符号为-1时, flag[i]=1,当雅可比符号为1时,flag[i]=0.根据这一分析我们可以最终恢复出flag.

Tips: If x is a quadratic residue and gcd(x,N)=1,then(x|N)=1.If the Jacobi symbol is 0, then x contains a factor of N.

解题脚本

#!/usr/bin/env python3
import gmpy2

N = 23981306327188221819291352455300124608114670714977979223022816906368788909398653961976023086718129607035805397846230124785550919468973090809881210560931396002918119995710297723411794214888622784232065592366390586879306041418300835178522354945438521139847806375923379136235993890801176301812907708937658277646761892297209069757559519399120988948212988924583632878840216559421398253025960456164998680766732013248599742397199862820924441357624187811402515396393385081892966284318521068948266144251848088067639941653475035145362236917008153460707675427945577597137822575880268720238301307972813226576071488632898694390629
e = 0x10001
two_inv = pow(gmpy2.invert(2, N), e, N)

with open('flag.enc', 'r') as f:
    flag = ''
    tmp = ''
    for ct in f:
        ct = int(ct.strip().rstrip('L'), 16)
        jacobi = gmpy2.jacobi(two_inv * ct, N)
        if jacobi == -1:
            tmp = '1' + tmp # 注意顺序 不是tmp += '1'
        else:
            tmp = '0' + tmp
        if len(tmp) == 8:
            flag = chr(int(tmp, 2)) + flag
    flag = chr(int(tmp, 2)) + flag

print(flag)

0x03 RSAchain

题目来源

2019-9-22 Teaser-Dragon ctf RSAchained

题目类型

Crypto,rsa,sagemath,partial private key explosure attack

题目描述

题目给出了加密脚本task.py以及加密之后的结果output.txt.加密脚本如下:

import os
import gmpy2

flag = int(open('flag.txt').read().encode("hex"), 16)

def genPrime(bits):
    data = os.urandom(bits/8)
    number = int(data.encode("hex"), 16)
    # gmpy2.next_prime()返回下一个可能的大于number的素数
    return gmpy2.next_prime(number)


e = 1667


# rsa1: p - 700 bits q - 1400 bits

p = genPrime(700)
q = genPrime(1400)

n = p*q
phi = (p-1)*(q-1)
d = gmpy2.powmod(e, -1, phi)

rsa1 = (n, d)

# rsa2: p - 700 bits, q - 700 bits, r = 700 bits

p = genPrime(700)
q = genPrime(700)
r = genPrime(700)

n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.powmod(e, -1, phi)

rsa2 = (n, d)

# rsa3: p - 700 bits, q - 700 bits, r = 700 bits

p = genPrime(700)
q = genPrime(700)

n = p*q*r
phi = (p-1)*(q-1)*(r-1)
d = gmpy2.powmod(e, -1, phi)

rsa3 = (n, d)

# rsa4: p - 700 bits, q - 700 bits

p = genPrime(700)
q = genPrime(700)

n = p*q*q
phi = (p-1)*(q-1)*q
d = gmpy2.powmod(e, -1, phi)

rsa4 = (n, d)

# 按照n从小到大进行排序
rsa = sorted([rsa1, rsa2, rsa3, rsa4])


for n, d in rsa:
    print 'pubkey:', n, d % (2**1050)
    flag = pow(flag, e, n)

print 'encrypted flag', flag

题目分析

拿到题目之后发现是一个链式rsa加密,明文经过四次加密得到密文.四次加密均采用rsa算法,加密指数e = 1667,并且模数n满足:

n1 = p1*q1
n2 = p2*q2*r
n3 = p3*q3*r
n4 = p4*q4*q4

除大素数r之外的p,q每轮都单独生成.将n1-n4从小到大排列之后对flag进行多次加密.观察每次加密的输出,每次输出排序后对应的n以及d % (2**1050).

简单分析之后,我们可以得出一些思路:首先观察四个模数,显然n2,n3具有公因数r,通过math.gcd()可以求出大素数r,并同时确定n2和n3的位置.然后我们会考虑到加密顺序的问题,由于上一步已经明确找出了n2和n3的位置,故确定n1,n4的顺序最多需要爆破两次.最后我们观察每次输出,给出了d % (2**1050),属于部分密钥暴露的情况,联想到使用partial private key explosure attack,但由于无法确定暴露的位数故存在失败的可能性.

这里我们通过分析n1-n4的构成可以从另一个角度解决问题.

Pretreatment: `e*d == 1 mod phi(N)`

将上式变形为e\*d-k*phi(N)=1.由于d<phi(N),故上式成立,则k<e,从而确定出k的爆破范围.将上式与d0建立转换联系,有:

e * d == 1 mod phi(N)
(e * d) mod 2**1050 == (1 mod phi(N)) mod 2**1050
(e mod 2**1050) * (d mod 2**1050) mod 2**1050 == (1 mod phi(N)) mod 2**1050
e * d0 == (1 mod phi(N)) mod 2**1050
e * d0 - k*phi(N) == 1 mod 2**1050

Case1: `N = pqr`

首先通过GCD函数求出大素数r的值以及n2,n3的位置.计算后发现r = 32619972550448885952992763634430245734911201344234854263395196070105784406551510361671421185736962007609664176708457560859146461127127352439294740476944600948487063407599124272043110271125538616418873138407229,n2,n3分别位于加密的第一、二位.

观察上一步处理得到的关系式e * d0 - k*phi(N) == 1 mod 2**1050,发现e,d0,k均为常数,于是联想到处理phi(N),由于phi(N) = (p-1)*(q-1)*(r-1),且N和r均为已知常数,故在方程两侧同乘变量进行变量转换,最终变成只包含p、N、r的方程:

(p-1)*(q-1)*(r-1) = 
(p-1)*(qr-q-r+1) = 
pqr-pq-pr+p-qr+q+r-1 = 
N-pq-pr+p-qr+q+r-1 = | *r
Nr-pqr-pr^2+pr-qr^2+qr+r^2-r =
Nr-N-pr^2+pr-qr^2+qr+r^2-r = |*p
Nrp-Np-p^2r^2+p^2r-pqr^2+pqr+pr^2-rp = 
Nrp-Np-p^2r^2+p^2r-Nr+N+pr^2-pr
final equation: e*d0*p*r - k*(Nrp-Np-p^2r^2+p^2r-Nr+N+pr^2-pr) == p*r mod 2**1050

最终解上述方程(使用sagemath)可以找出p2,p3的值,成功分解n2,n3.

Case2: `N = p*q**2`

此种情况下,我们有如下信息:phi(N) = (p-1)*(q-1)*q,N = p*q^2.我们使用和前一种情况相同的方法进行方程转化.由于只有q的最高次数为2,所以将q作为未知参数进行转换:

(p-1)*(q-1)*q = 
(p-1)*(q^2-q) = 
pq^2-pq-q^2+q = 
N-pq-q^2+q = | *q
Nq-pq^2-q^3+q^2 = 
Nq-N-q^3+q^2
final equation: e*d0*q - k*(Nq-N-q^3+q^2) == q mod 2**1050

尽管我们无法确定最后两个密钥对应的顺序,我们只需要最多进行两次尝试就可以进行正确分解,从而得到q4,成功分解n4.

Case3: `N = p*q` and `q.nbits() == 1400`

这种情况下,分解方法同上面的一样:

(p-1)*(q-1) = 
pq-p-q+1 = 
N-p-q+1 = |*p
Np-p^2-pq+p =
Np-p^2-N+p
final equation: e*d0*p - k*(Np-p^2-N+p) == p mod 2**1050

成功分解n1之后依次解密可以得到最终的flag.

解题脚本

Case1: N = p*q*r

# exp.sage
def find_p(d0, e, n, start, stop):
    r = 32619972550448885952992763634430245734911201344234854263395196070105784406551510361671421185736962007609664176708457560859146461127127352439294740476944600948487063407599124272043110271125538616418873138407229
    X = var('X')
    for k in xrange(start, stop):
        print("test for", k)
        results = solve_mod([e*d0*r*X - k*(n*r*X -n*X - X*X*r*r + X*X*r - n*r + n +X*r*r - X*r) == X*r], 2^1050)
        for x in results:
            p0 = ZZ(x[0])
            if is_prime(p0) and gcd(n,p0)!=1:
                return p0

Case2: N = p*q^2

将上述函数的方程改为results = solve_mod([e*d0*X - k*(n*X-n-X*X*X + X*X) == X], 2^1050)即可.

Case3: N = p*q and q.nbits() == 1400

将关键函数改为results = solve_mod([e*d0*X - k*(n*X-X*X-n+X) == X], 2^1050)即可.

得到所有参数之后直接解密:

import gmpy2
from Crypto.Util import number

e = 1667

def solve():
    r = calculated_r
    assert gmpy2.is_prime(r)
    n1 = given_n1
    p1 = 90298557884682577669238320760096423994217812898822512514104930945042122418007925771281125855142645396913218673571816112036657123492733042972301983242487835472292994595416656844378721884370309120262139835889657
    q1 = (n1 // r) // p1
    assert gmpy2.is_prime(q1)
    assert gmpy2.is_prime(p1)
    d1 = gmpy2.invert(e, (p1 - 1) * (q1 - 1) * (r - 1))

    n2 = given_n2
    p2 = 142270506848638924547091203976235495577725242858694711068289574174127601000137457280276860615471044907560710121669055364010408768146949985099404319539891688093875478389341632242096859500255283810703767020918479
    q2 = (n2 // r) // p2
    assert gmpy2.is_prime(q2)
    assert gmpy2.is_prime(p2)
    d2 = gmpy2.invert(e, (p2 - 1) * (q2 - 1) * (r - 1))

    q3 = 267307309343866797026967908679365544381223264502857628608660439661084648014195234872217075156454448820508389018205344581075300847474799458610853350116251989700007053821013120164193801622760845268409925117073227
    n3 = given_n3
    p3 = n3 // (q3 * q3)
    assert gmpy2.is_prime(q3)
    assert gmpy2.is_prime(p3)
    d3 = gmpy2.invert(e, (p3 - 1) * (q3 - 1) * q3)

    p4 = 188689169745401648234984799686937623590015544678958930140026860499157441295507274434268349194461155162481283679350641089523071656015001291946438485044113564467435184782104140072331748380561726605546500856968771
    n4 = given_n4
    q4 = n4 // p4
    assert gmpy2.is_prime(q4)
    assert gmpy2.is_prime(p4)
    d4 = gmpy2.invert(e, (p4 - 1) * (q4 - 1))

    ct = ciphertext

    rsa1 = (n1, d1)
    rsa2 = (n2, d2)
    rsa3 = (n3, d3)
    rsa4 = (n4, d4)

    rsa = sorted([rsa1, rsa2, rsa3, rsa4], reverse=True)

    for n, d in rsa:
        ct = pow(ct, d, n)
    print(number.long_to_bytes(ct))


solve()

0x04 总结

这两道题目分别运用了雅可比符号和方程化简的知识点.第二道题目使用sagemath这一工具快速解决模域方程问题,但sagemath的效率较低(可以考虑并行编程).

折腾了好久终于成功安装上sagemath这一数学工具,但爆破效率也太低了吧….需要抽个时间好好研究一下sage编程.

0x00 几句废话

0x01 数学知识补充

Legendre symbol

Jacobi symbol

0x02 Application of jacobi symbol

计算雅可比符号的python函数 gmpy2.jacobi()

题目来源

题目类型

题目描述

题目分析

解题脚本

0x03 RSAchain

题目来源

题目类型

题目描述

题目分析

Pretreatment: e*d == 1 mod phi(N)

Case1: N = p*q*r

Case2: N = p*q**2

Case3: N = p*q and q.nbits() == 1400

解题脚本

0x04 总结

计算雅可比符号的python函数 `gmpy2.jacobi()`

Pretreatment: `e*d == 1 mod phi(N)`

Case1: `N = pqr`

Case2: `N = p*q**2`

Case3: `N = p*q` and `q.nbits() == 1400`