RSA-Coppersmith相关攻击

0x00 基本原理

Coppersmith相关攻击与Don Coppersmith紧密相关,他提出一种针对于模多项式(单变量,二元变量,甚至多元变量)找所有小整数根的多项式时间的方法.

这里以单变量为主进行介绍,假设:

• 模数为N,N具有一个因子$ b>=N^ \beta $, $ 0< \beta <=1$
• 多项式F的次数为$\delta$

那么该方法可以在$ O(c \delta ^{5log^9(N)}) $的复杂度内找到该多项式所有的根x0,这里我们要求$|x0| < cN^(\beta ^2/ \delta) $.

在这个问题中,我们的目标是找到模N意义下多项式所有的根,这一问题被认为是复杂的.Coppersmith method主要通过LLL方法找到

• 与该多项式具有相同根x0
• 更小系数
• 定义域为整数域

的多项式g,由于在整数域上找多项式的根是简单的,从而我们就得到了原多项式在模意义下的整数根.

问题的关键则变成从f转换到g,Howgrave-Graham给出了一种思路:

在LLL算法中,有两点是非常有用的

• 只对原来的基向量进行整数线性变换,这可以使得我们在得到g时,仍然以原来的x0为根.
• 生成的新的基向量的模长是有界的,这可以使得我们利用Howgrave-Graham定理.

在这样的基础上,我们再构造出多项式族g就可以了.需要注意的是,由于Coppersmith根的约束,在RSA中的应用时,往往只适用于e较小的情况.

• 攻击脚本:coppersmith.sage
• 参考链接

0x01 Related Message Attack

攻击条件

Alice使用相同的N和e对两个相关的信息m1,m2进行加密,并将加密之后的结果c1,c2发送给Bob.并且m1,m2满足

$$m1 \equiv f(m2) mod N$$

其中f为一个线性函数,即$ f=a*x+b $.

在具有较小错误概率的情况下,复杂度为$ O(elog^2(N)) $.

攻击原理

首先我们知道$ c1\equiv m1^e mod N $,并且$ m1 \equiv f(m2) mod N $,那么我们可以知道m2是$ f(x)^e \equiv c1 mod N $的一个解,即它是方程$ f(x)^e-c1 $在模N意义下的一个根.同样,m2是$ x^e $模N意义下的一个根.所以说$ x-m2 $同时整除以上两个多项式.因此,我们可以求得两个多项式的最大公因子,如果最大公因子恰好是线性的话,那么我们就求得了m2.需要注意的是,在e=3的情况下,最大公因子一定是线性的.

当e=3,且$ f(x)=a*x+b $的情况下,经过推导我们可以得到:

$$m2 \equiv (2*a^3*b*c2-b^4+c1*b)/(a*c1-a^4*c2+2*a*b^3) \equiv (b/a)*(c1+2*a^3*c2-b^3)/(c1-a^3*c2+2*b^3)$$

上面的式子中右边所有的参数都是已知的,所以可以求得对应的信息.

典型例题

题目来源: SCTF RSA3

题目分析: 首先,跟踪TCP流我们发现,加密方式是将明文加上用户的user-id进行加密,而且还存在多组.我们选择模数相同的两个cipher.

解密脚本:

# exp.py
import gmpy2
id1 = 1002
id2 = 2614

c1 = number_c1
c2 = number_c2
n = number_n

# 构造f(x) = a*x+b
a = 1
b = id1 - id2


def getmessage(a, b, c1, c2, n):
    b3 = gmpy2.powmod(b, 3, n)
    part1 = b * (c1 + 2 * c2 - b3) % n
    part2 = a * (c1 - c2 + 2 * b3) % n
    part2 = gmpy2.invert(part2, n)
    return part1 * part2 % n


message = getmessage(a, b, c1, c2, n) - id2
message = hex(message)[2:]
if len(message) % 2 != 0:
    message = '0' + message

print message.decode('hex')

# exp.sage
import binascii

def attack(c1, c2, b, e, n):
    PR.<x>=PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+b)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

c1 = number_c1
c2 = number_c2
n = number_n
e=3
a = 1
id1 = 1002
id2 = 2614
b = id2 - id1
m1 = attack(c1,c2, b,e,n)
print binascii.unhexlify("%x" % int(m1 - id1))

0x02 Known High Bits Message Attack / Stereotyped Messages

攻击条件

普通的RSA解密模型如下:

$$c \equiv m^d mod N$$

并且假设我们知道消息m的大部分m0,从而m=m0+x,x即为待求消息.那么我们可以通过该方法进行消息恢复.这里待求的x其实就是满足Coppersmith约束的多项式的根.

攻击原理

我们构造多项式f(x) = (m+x)^e - c,其在模N条件下的根即为与m的差距.

攻击脚本

# exp.py
load("coppersmith.sage")
N = #N的值
e = #e的值
m = #m的大概值
c = #c的值
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
f = (m + x)^e - c
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon))
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

• 注意: XX是根的上界,根据所知的m的位数进行调整

0x03 Factoring with High Bits Known

攻击条件

当我们知道一个公钥中模数N的一个因子的较高位时,就有一定的几率来分解N.

攻击原理

我们在RSA攻击过程中需要进行模数N的分解,当已知其中一个大素数q的部分位时,可以构造函数f(x) = x-q',该式在模q条件下的根即为q’与q之间可能的差距.

攻击脚本

load("coppersmith.sage")
N = #N的值
ZmodN = Zmod(N)
P.<x> = PolynomialRing(ZmodN)
qbar = #q的近似值
f = x - qbar
beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)

• 注意必须满足q>=N^beta,所以这里令beta=0.5,保证两个因数中必有一个满足条件
• XX是f(x) = q'+x在模q意义下的根的上界,自然我们可以选择调整它,这里也表明了我们已知的q’与因数q之间可能的差距

典型例题

题目来源: 2017 WHCTF-UNTITLED

题目描述: 下载附件之后得到如下脚本.

from Crypto.Util.number import getPrime,long_to_bytes,bytes_to_long
import primefac
import time
from os import urandom
import hashlib
import sys
class Unbuffered(object):
    def __init__(self, stream):
        self.stream = stream
    def write(self, data):
        self.stream.write(data)
        self.stream.flush()
    def __getattr__(self, attr):
        return getattr(self.stream, attr)
import sys
sys.stdout = Unbuffered(sys.stdout)
def gen_args():
    p=getPrime(1024)
    q=getPrime(1024)
    n=p*q
    e=0x10001
    d=primefac.modinv(e,(p-1)*(q-1))%((p-1)*(q-1))
    return (p,q,e,n,d)
def proof():
    salt=urandom(4)
    print salt.encode("base64"),
    proof=raw_input("show me your work: ")
    if hashlib.md5(salt+proof.decode("base64")).hexdigest().startswith("0000"):
    print "checked success"
        return 1
    return 0

def run():
    if not proof():
        return
    m=int(open("/home/bibi/PycharmProjects/work/whctf/flag","r").read().encode("hex"),16)#flag{*}
    (p,q,e,n,d)=gen_args()
    c=pow(m,e,n)
    print "n:",hex(n)
    print "e:",hex(e)
    print "c:",hex(c)
    t=int(hex(m)[2:][0:8],16)
    u=pow(t,e,n)
    print "u:",hex(u)
    print "===="
    x=int(hex(m)[2:][0:8]+raw_input("x: "),16)
    print "===="
    y=int(raw_input("y: "),16)
    if (pow(x,e,n)==y and pow(y,d,n)==t):
        print "s:",hex(int(bin(p)[2:][0:568],2))
51 run()

题目分析: 首先要绕过proof()函数的验证,即要满足hashlib.md5(salt+proof.decode("base64")).hexdigest().startswith("0000"),这里可以使用脚本爆破,使盐值和输入内容的base64解码开头四位为0000.
将爆破结果随便提交一个,即可通过验证,得到n,e,c,u.

再分析题目所给的py脚本,可以看出:

• c是flag经过RSA加密后的密文,其中n和e已知
• u为m的前8位(即为f)经过RSA加密后的值

• x=int(hex(m)[2:][0:8]+raw_input("x: "),16)
  y=int(raw_input("y: "),16)
  pow(x,e,n)==y and pow(y,d,n)==t

将以上三行连起来分析,令x为空,y为u即可通过最后一步if验证,从而得到p的前568位.

现在我们得到了以下信息:

flag加密后的密文c
加密所用到的n和e
p的前568位

容易联想到恢复p再解RSA问题.

这里联想到使用Coppersmith Attack,该方法需要至少576位p,已知568位,差了两个十六进制数,根据官方提示进行爆破,代码如下:

# explore.sage
n = 0x621725fc8ce7ce38c3ff9da9e7d4a9d8764eac78985f5abcf52bbad15f172d76c0d9cc4b08b1bbcd36590bc0050ab492f7df58404c0bca8b178e7e0f07c0c08e46ae63d8248b1f1cdd3f6cfed6fcc348b62e1cb7b269fc800c77d303ae154e1ade78a7492158c80818b8b180699e709764d31e08544e9c6dd75788d468ce1288927d5cea4336d6a76a9998731e15285c4695550c4db7210d09168903774ccee5dda6f8d3a502f8eac38a97c0cd84b3c3be87751dfc9f3bbcdec881d20fc7cb0086f71a0146b2e11e688372f809e401b9f19c003f75920df962631127dbda84cc781870b7895382c02d726eabc8373e73aec38f0a1dad4b8d0060c47511ef75d3
p = 0xb447abcd768378f05675b98f4724e934b1a7251749b14b11d3af19d3a47e98dbf90b94a77a01ab76e6a7f99d5b79cfce8e9edfcc7b626ed0f1699d743fa78bd73ff4a03f904bde

import string
dic = string.digits + "abcdef"

for a in dic:
    for b in dic:
        pp = hex(p) + a + b
        #p需要用0补全到1024位
        pp += '0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000'
        #要加的数字与补全p时0的个数有关
        pp = int(pp, 16)
        p_fake = pp+0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
        pbits = 1024
        kbits = pbits-576
        pbar = p_fake & (2^pbits-2^kbits)
        print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
        PR.<x> = PolynomialRing(Zmod(n))
        f = x + pbar
        try:
            x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
            print x0 + pbar
        except:
            pass

得到p之后就可以正常解开RSA得flag了.

0x04 Boneh and Durfee Attack

攻击条件

当d较小时,满足d<N^(0.292)时,我们可以利用该攻击,比维纳攻击效率高一些.

攻击原理

首先有$ e*d \equiv 1 mod (\phi(N)/2) $

进而转化为$ ed + k\phi(N)/2 = 1 $

即$ k* \phi(N)/2 \equiv 1 mod e $

又$ \phi(N) = (p-1)*(q-1) = N-p-q+1 $

所以$ k*(N-p-q+1)/2 \equiv 1 mod e $

这里令$ A = (N+1)/2 $, $ y = (-p-q)/2 $,原式为:

$ f(k,y) = k*(A+y) \equiv 1 mod e $

其中$ |k| < (2ed)/\phi(N) < (3ed)/N = 3(e/N)d < 3(e/N)N^\delta, |y| < 2*N^0.5 $

这里delta为预估的小于0.292的值.

如果我们可以求出该二元方程的根,就可解一元二次方程N=p*q,p+q=-2*y来得到p与q.

攻击脚本

攻击工具: boneh_durfee.sage

注意事项:

• 根据boneh_durfee.sage脚本后的使用说明替换解密参数.变量delta是对私钥d的估计.如果不满足d<N^delta这一条件,则无解.从delta=0.26开始逐渐递增,最大不超过0.292
• 如果脚本报错: “Try with highers m and t”,则应该增大m的值,相应的计算时间会增加
• 如果由于解密时间太长而不愿增大m,则可以尝试减小x的值,因为可能出现x的设定值与真实值差距过大的情况.
• 如果仍然无法找到delta,m和t,则可以尝试在d<N^0.292的范围内进行爆破.
• 一旦发现x,y的可能解,则可以将其插入如下等式:e*d=x*[(N+1)/2+y]+1

典型例题

题目来源: 2015 PlaidCTF Curious

题目分析: 该题目给了一堆N, e, c.简单看一下可以发现e比较大.这个时候可以考虑维纳攻击或Boneh_durfee攻击.

解题脚本(核心代码):

nlist = list()
elist = list()
clist = list()
with open('captured') as f:
    # read the line {N : e : c} and do nothing with it
    f.readline()
    for i in f.readlines():
        (N, e, c) = i[1:-2].split(" : ")
        nlist.append(long(N,16))
        elist.append(long(e,16))
        clist.append(long(c,16))

    for i in range(len(nlist)):
        print 'index i'
        n = nlist[i]
        e = elist[i]
        c = clist[i]
        d = solve(n,e)
        if d==0:
            continue
        else:
            m = power_mod(c, d, n)
            hex_string = "%x" % m
            import binascii
            print "the plaintext:", binascii.unhexlify(hex_string)
            return

0x05 Partial Key Exposure Attack

攻击条件

若e较小,且d的低位已知时,可以考虑使用部分私钥泄露攻击.

攻击原理

部分私钥泄露攻击的原理同前面提到的明文高位泄露以及模数部分泄露原理相同.

攻击脚本

# partial_key_exposure_attack.sage
def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p


if __name__ == '__main__':
    n = number_n
    e = 3
    d = number_d

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

其中d0代表已知d的较低位,kbits是已知的d0的位数.

0x06 题目举例

下面以一道CTF题目为例,讲解上述几种攻击方法的具体应用.另外一道综合类RSA题目链接如下: 2018 护网杯-nextrsa

题目来源: 2019 护网杯-Copperstudy

复现地址: buuoj-Crypto-Copperstudy

题目描述: 题目给出了一共六个challenge,只有全部通过验证才可以得到最终的flag.我们针对不同的challenge分别使用sage脚本解题,再逐个提交.

下面进行题目分析

Challenge0 — SHA256 proof

[+]proof: skr=os.urandom(8)
[+]hashlib.sha256(skr).hexdigest()=str(hashlib.sha256(skr).hexdigest())
[+]skr[0:5].encode(\'hex\')=str(skr[0:5].encode('hex'))
[-]skr.encode(\'hex\')=

nc之后返回上述代码,给出了八位字符串经过sha256之后的结果以及前五位的sha256之后的结果,爆破后三位传上去,可以进入下一个挑战.

Challenge1 — Known High Bits Message Attack

[+]Generating challenge 1
[+]n=0x331e53d1808798def926bc2c8081b3a959cec19c04ad6dd3a25357b5e3889dc0bbb8618b80ddecca89494eec6015080cf4402fcef0971f76d978c517ab1e3019ae65fdc443a99036d4adcda780dd662ae3eb5d3c6ce68adfe38137689df75a6196a7a6dc94a681dfb5437439c810416112b250402f53eb2341df2145c569c135L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xab7b8544dc18a13c221d33b8ea84ee69ea3c74a1ce123e6f0a565e6afaff3d2682dfa254170a1200d66e9c017727c43b3c1af221f81d90598741454f68448cef4128ff56bb9929ffd3edaaa8069c08293463ad20486b6e6bee654ab471a3b364122d41f4570f6aa1084eb1eda5eebde1436a488e0390f8057df835f323802d4L
[+]((m>>72)<<72)=0x858be94f2f6253ac4586da573086221c8256bf7fe7c7f6d0d4e459fd28abf8883cfa225f5cbb519d2c8e0427aab1dc03979886ac104018000000000000000000L
[-]long_to_bytes(m).encode('hex')=

题目给出的e较小,而且只隐藏了明文m的低72位.联想使用Stereotyped messages攻击.脚本如下:

n = given_n
e = 3
m = randrange(n)
c = pow(m, e, n)
beta = 1
epsilon = beta^2/7
nbits = n.nbits()
kbits = floor(nbits*(beta^2/e-epsilon))
mbar = given_high_bits_of_m
c = given_c
print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)
PR.<x> = PolynomialRing(Zmod(n))
f = (mbar + x)^e - c
print m
x0 = f.small_roots(X=2^kbits, beta=1)[0]  # find root < 2^kbits with factor = n
print mbar + x0
print x0

challenge2—Factoring with High Bits Known

[+]Generating challenge 2
[+]n=0x116c51f73ef1c6b3b890dd8be446b80ac1dbe93742348e1284a7fdf0c76604ceae72011918f18de6b0ab873500ef2ed351110b67acce5b8c48a750a376c3e0117c44ec58e84e35f2ebf0e553b718720952dc826e364f130c2839c76878e0bfb3be0f24b06b3d91f1655e7ce588d2a3c429901197012db4d8b802308072bfca3fL
[+]e=65537
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x8d8fba82b1ca4e8a6e87b1ed5d50a9e6e49b3fb2aed78208e8c513842dedb5f14b82b39e03ea86089e76b59ff7bec0f6647096098346dcf64c7d1aaf533f99827fd9979dee217c511a3192e99a70d4fcd6aa44b2cf52a1ceddf99db42cbf2872e7e2ed421a4a9ff548bef6dfdad7ef17b09748bdf0025dfb93091e11115ebd4L
[+]((p>>128)<<128)=0x2bff4035e24f2023f876abaf53ef53374d0208d59d4350a1cf356050c3a09cfc644d9c46cb59f013fadd96bea4a56dd100000000000000000000000000000000L
[-]long_to_bytes(m).encode('hex')=

该挑战给出了其中一个模数p除了低128bits的其他信息.联想使用factoring with high bits known攻击.脚本如下:

n=given_n
p=given_high_bits_of_p
p_fake = p+0x10000000000000000000000000
pbits = 1024
kbits = pbits-576
pbar = p_fake & (2^pbits-2^kbits)
print "upper %d bits (of %d bits) is given" % (pbits-kbits, pbits)
PR.<x> = PolynomialRing(Zmod(n))
f = x + pbar
x0 = f.small_roots(X=2^kbits, beta=0.4)[0]  # find root < 2^kbits with factor >= n^0.4
print x0 + pbar

Challenge3 — Partial Key Exposure Attack

[+]Generating challenge 3
[+]n=0x56705388192a25439c7ec9f826467255aeac3a1991b0a5804e8cbe01d4fd33c0accdacc8cb2497969133116d841032cd023f29e4014b0c7619c40ce6e1977308f3587da928fe7c103e8fd68c0e909d229e68c23879c010f88dca4481af1c7030466edc93898b12f31dba9e7aa513fb1fd84c3d1d028cc068160501dafa1d54bL
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xcbe7d8021fa02b92239521aeaaf76b2d9553b6b738c79a2c31ef9dcef7875d5bde76f5ebb318660761090869c02c182a29516482e5daf090df76d10eab9398ede85a00d47abb3e27f6a87f8c0928e18c778efb3b6a02acb52257369cbc7e3015bda888e50d5586a34a5554df1f5f0e4cb0b8e9dd442ed939f610d18731be3L
[+]d=invmod(e,(p-1)*(q-1))
[+]d&((1<<512)-1)=0xd74e2c4973ea6530620197a999a7a78d85a3029dfe8931397ee15b480c2f77b5042938e2f58f60e9c44e4f8d911b661b42dac0dbc0c1513773f870916b2418abL
[-]long_to_bytes(m).encode('hex')=

题目给出了低加密指数及d的部分位数,于是使用Partial key exposure attack攻击,脚本如下:

def partial_p(p0, kbits, n):
    PR.<x> = PolynomialRing(Zmod(n))
    nbits = n.nbits()

    f = 2^kbits*x + p0
    f = f.monic()
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
        x0 = roots[0]
        p = gcd(2^kbits*x0 + p0, n)
        return ZZ(p)

def find_p(d0, kbits, e, n):
    X = var('X')

    for k in xrange(1, e+1):
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
        for x in results:
            p0 = ZZ(x[0])
            p = partial_p(p0, kbits, n)
            if p:
                return p

if __name__ == '__main__':
    n = given_n
    e = 3
    d = known_d

    beta = 0.5
    epsilon = beta^2/7

    nbits = n.nbits()
    kbits = floor(nbits*(beta^2+epsilon))
    d0 = d & (2^kbits-1)
    print "lower %d bits (of %d bits) is given" % (kbits, nbits)

    p = find_p(d0, kbits, e, n)
    print "found p: %d" % p
    q = n//p
    print d
    print inverse_mod(e, (p-1)*(q-1))

Challenge4 — Basic Broadcast Attack

[+]Generating challenge 4
[+]e=3
[+]m=random.getrandbits(512)
[+]n1=0x9c94fecac76f9c5524d994d51efc1f02ad40fcf9cd5409d7c9f86a9f10e31b6c73d8bc02df743fea939acbcf9f81a748914fce0f8df1155c0f29faac38bd70b322eb7bc69c130720bdcb2ad2cbb84ad182b36e93170d81cb3a68969c850519e86b6a3676534cdbe85c9429c058230d58527d8028c134d6078cbb89faa071848fL
[+]c1=pow(m,e,n1)=0x5e3b988abb38c33e145bbc16f56ec192253d26cc053d4f78e073d0d035eda4ea91f33ec7f7cd1a56165cae95a86e0a4edabb83743966b3a4621bb33753aec5fa4b1c6d80e0d404c19c6659c8ff6dc4f5539a5dbae659ca4f24f4c53a65c5c42bf9de04852c098841d2affe83c59be99b6ecd857e232cb008c657e1f55137bf06L
[+]n2=0x409a8a39fcb302f0660f0a85b6d43636dce5b4797b6f3ef0b4972f70b6e0c74038c55ba50e0c918057e9ceaee024ae81da2faede8b5b66caae6892943a8892ad98b1f6f208b8b5ded753e6b8c6b94c5faf67314384f3f26e3dca579237893f098c90b0f8b80692aed4606947d656b74b69444ba0dc24b9c66a339f7a50f52783L
[+]c2=pow(m,e,n2)=0xc5381d89ca5be27f43c30dbc395ce0d5b8a69adb80dc05d7f5d8dffc1b2fb76d2ab656f5659b9280c9cac83addcc0eb58e86f8e07a37f28b0500ab75bde4eb2b2e6631eeeb6bbe146c889b2ac6046864977aaee7292676fdbd4fb987940a83a94c3d04aef256b50d304d945528c69866acf591f914c0e50e012734827143ed7L
[+]n3=0x56a700d8f04da68c6cdb08e04a0cb2fa332389e10c1a3c94b220cb39144fc971c804ab02637303866040c13814194d863814453eec48db6136741d3a599cf890c678114b65dc60da2bbd29651bd0148f8949d69c4b18460ad0e1908eba384a1b51041e41caf70fed285fb34a8e56f04487d6d8b5d88f2a88d88565ef6757a697L
[+]c3=pow(m,e,n3)=0x73e58f11dd9f637a7a7c05f6223ee95cb6d34a77583bfc6ca675955d51dd15ff4561654264e9985fcb2e87e3ddda7d6d7620cee80a1f2c20944d5d6f456a3e892f74b6745ddecbe3447825bf44344fc9e0839bdaebcca8352075675ffc8fee8c3698a87f3110f4004fea88c3faf05e5a527854e759e315b487b49e8ff9510cbL
[-]long_to_bytes(m).encode('hex')=

题目给出三组使用小指数e=3加密的消息,考虑使用广播攻击.

import gmpy
import gmpy2
def modinv(a, m):
    return int(gmpy2.invert(a, m))
def chinese_remainder(n, a):
    sum = 0
    prod = reduce(lambda a, b: a * b, n)
    for n_i, a_i in zip(n, a):
        p = prod / n_i
        sum += a_i * modinv(p, n_i) * p
    me = int(sum % prod)
    return gmpy.mpz(me).root(len(n))[0]
    ns = given_ns
    cs = given_cs
    m = chinese_remainder(ns, cs)
    print m

Challenge5 — Related Message Attack

[+]Generating challenge 5
[+]n=0x1bda683489ec09b15aa5ab9356db56e8586f03879e19bf4b2316b56332fd2d994ae8682d121373b21771eda5246b3565c52266e83bada43723bb8f4457d712f339d350d02bcd257923fb6b7ad265bafd4b9429943ba56f0d27b123962adf60b809f886a090e3472abe01e194dbc3ec1ecba2550d695e771d3f0edb9ada77f29L
[+]e=3
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0x22573b528e5ca137dc93b7f17f04d4efbf82124215a9c28ae6823fe5c7b6fb5eb5d328d9f6dbf73f88f59add74630d0721a822f8fb884b314f4c45aae1358fc8a19c59bbc370463541d58bd9cda1d77575a443cfbd85bdba48ae3e01642811a0b9824e3c8df8c02caed7a0606ceb6695dca7372e4291c60a98ed56b9442434L
[+]x=pow(m+1,e,n)=0xe5ac2d53cd385143472febb8d7ba4acb7697bd494ef9ea0d165dd2ba7e451d803e45076ded5ef44bec0b72052b932348a50f0c66c6641159518f5137140a4db9fc497982930801715468932913e257f8b2abe287244d1d087c0ecf679cb46b1957bef678dee094d650a97d5a9d53cab80986571d890fbcd024528d6a321ac9L
[-]long_to_bytes(m).encode('hex')=

题目给出m和m+1加密之后的消息c1,c2,且加密指数e=3.考虑到可以使用相关明文攻击.令a=1,b=-1,构造payload如下:

import hashlib
import gmpy2
import libnum
from Crypto.Util.number import *
 
n = given_n
e = 3
 
c1 = number_c1
c2 = number_c2


a = 1
b = -1
padding2 = 1
def getM2(a,b,c1,c2,n):
    a3 = pow(a,3,n)
    b3 = pow(b,3,n)
    first = c1-a3*c2+2*b3
    first = first % n
    second = 3*b*(a3*c2-b3)
    second = second % n
    third = second*gmpy2.invert(first,n)
    third = third % n
    fourth = (third+b)*gmpy2.invert(a,n)
    return fourth % n
m = getM2(a,b,c1,c2,n)-padding2
print "m==\n" + hex(m) + "\n"

#print m
c = pow(m,e,n)
#print hex(c)
if c == c1:
    print "yeah"

Challenge6 — Boneh and Durfee Attack

[+]Generating challenge 6
[+]n=0xbadd260d14ea665b62e7d2e634f20a6382ac369cd44017305b69cf3a2694667ee651acded7085e0757d169b090f29f3f86fec255746674ffa8a6a3e1c9e1861003eb39f82cf74d84cc18e345f60865f998b33fc182a1a4ffa71f5ae48a1b5cb4c5f154b0997dc9b001e441815ce59c6c825f064fdca678858758dc2cebbc4d27L
[+]d=random.getrandbits(1024*0.270)
[+]e=invmod(d,phin)
[+]hex(e)=0x11722b54dd6f3ad9ce81da6f6ecb0acaf2cbc3885841d08b32abc0672d1a7293f9856db8f9407dc05f6f373a2d9246752a7cc7b1b6923f1827adfaeefc811e6e5989cce9f00897cfc1fc57987cce4862b5343bc8e91ddf2bd9e23aea9316a69f28f407cfe324d546a7dde13eb0bd052f694aefe8ec0f5298800277dbab4a33bbL
[+]m=random.getrandbits(512)
[+]c=pow(m,e,n)=0xe3505f41ec936cf6bd8ae344bfec85746dc7d87a5943b3a7136482dd7b980f68f52c887585d1c7ca099310c4da2f70d4d5345d3641428797030177da6cc0d41e7b28d0abce694157c611697df8d0add3d900c00f778ac3428f341f47ecc4d868c6c5de0724b0c3403296d84f26736aa66f7905d498fa1862ca59e97f8f866cL
[-]long_to_bytes(m).encode('hex')=

根据题目所给信息可知d < N^0.25,使用低指数解密后提交可得最后的flag.