Fetching...

-

Just a minute...

Updated on exploration

关键词：rsa，coppersmith攻击。

CopperSmith攻击的种类真的很多，以下是我归纳的几种常见形式：

一道新的例题——p的高位和地位泄露

摘自：Securinets CTF Quals 2020 - Destruction

题目中提及MSB寓意即最高比特位，LSB即最低比特位，根据铜匠攻击即可,sage脚本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
size = 512
sizep=256
knownbits= 134
N=14086160291425342283520344380411983364812792954622400251334758082442316624175006850950987254617679940795136231914925367368535278968830499182004816257654049

#we need to define an polynomial == 0 (mod p) that gives us the missing part (x)
# f_p(x) = x*2**(knownbits/2) + p_msb + p_lsb
# it's not monic so we need to divide by 2**(knownbits/2)
# set R = 2**(knownbits/2) and invert it modulo N

R = 2**(knownbits/2)#从第68位开始测试
invR = inverse_mod(R,N)
#补齐两边
p_msb = 251000163339563476196 << (sizep-knownbits/2-1)
p_lsb=int('2567fcb8c35e6dc63',16)
#setup coppersmith
F.<x> = PolynomialRing(Zmod(N))
#define the poly in x modulo p
f = x + (p_msb+p_lsb)*invR
#solve it
x0 = f.small_roots(X=2^(sizep-knownbits)-1, beta=0.44, epsilon=1/64)[0]

 

print ("reconstructed p: {:x}".format(Integer(x0*R)+p_msb+p_lsb))

在这道题目中，p的高位和地位比特都被泄露，可以解出rsa明文。

引申与补充

除了上述例题所述的情况外，我目前至少见过四种coppersmith攻击模式。

2019强网杯-RSA-Coppersmith

1.challenge 1

已知明文的高位，是Stereotyped messages攻击 或 Lattice based attacks 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = #输入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 = m & (2^nbits-2^kbits)
c = 0x1f6f6a8e61f7b5ad8bef738f4376a96724192d8da1e3689dec7ce5d1df615e0910803317f9bafb6671ffe722e0292ce76cca399f2af1952dd31a61b37019da9cf27f82c3ecd4befc03c557efe1a5a29f9bb73c0239f62ed951955718ac0eaa3f60a4c415ef064ea33bbd61abe127c6fc808c0edb034c52c45bd20a219317fb75
 
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 = n1
 
print mbar + x0

2.challenge 2

已知p的高位，Factoring with High Bits Known

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = 0x5894f869d1aecee379e2cb60ff7314d18dbd383e0c9f32e7f7b4dc8bd47535d4f3512ce6a23b0251049346fede745d116ba8d27bcc4d7c18cfbd86c7d065841788fcd600d5b3ac5f6bb1e111f265994e550369ddd86e20f615606bf21169636d153b6dfee4472b5a3cb111d0779d02d9861cc724d389eb2c07a71a7b3941da7dL
p_fake = 0x5d33504b4e3bd2ffb628b5c447c4a7152a9f37dc4bcc8f376f64000fa96eb97c0af445e3b2c03926a4aa4542918c601000000000000000000000000000000000L
 
 
 
 
#pbits = 2048
pbits = p_fake.nbits()
#kbits = 900
kbits = 128  #p失去的低位
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.3
p= x0 + pbar
print p

3.challenge 3

已知私钥的512位的低位 Partial Key Exposure Attack(部分私钥暴露攻击)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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 = 0xd463feb999c9292e25acd7f98d49a13413df2c4e74820136e739281bb394a73f2d1e6b53066932f50a73310360e5a5c622507d8662dadaef860b3266222129fd645eb74a0207af9bd79a9794f4bd21f32841ce9e1700b0b049cfadb760993fcfc7c65eca63904aa197df306cad8720b1b228484629cf967d808c13f6caef94a9
    e = 3
    d = 0x603d033f2ef6c759aec839f132a45215fc8a635b757f3951a731fe60bc6729b3bcf819b57abfcaba3a93e9edef766c0d499cad3f7adb306bcf1645cfb63400e3
    beta = 0.5
    epsilon = beta^2/7
    nbits = n.nbits()
    print "nbits:%d:"%(nbits) 
    #kbits = floor(nbits*(beta^2+epsilon))
    kbits = nbits - d.nbits()-1
    print "kbits:%d"%(kbits)
    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))

私钥泄露

这部分学习的是在网上看到的一道题目的一篇wp写的，都说密钥时现代密码的弱点，所以rsa私钥部分泄露原来也可以导致对rsa的铜匠攻击！这部分的方程倒不难推算，因此我也出了一道和私钥泄露有关的题目,题解也在博客里。这里把sage脚本也放出来吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
e=863
n = 100518394843898371534434468452366727877002363101196571557097132988734353726584916462381290904798733002716305256677572628142627545744681541293793069726231800754314572981168235829239563613754713724345581918566947492170647540708428013292098065584617876680109166595710006367308500341766024651457023537770009981295726110940010220082434490215229951191714998895277291076151298363584672162765486380515325199053994651202708865071379999942193926154807059329464291992287421875356468218685095369057734586073271903432589401520355996027480658214090147502829069822606753125953586123331154015992246394834867237734405963056883227552074835515815968441
c=86032824638305503499105979004374728344861493802341583733786447138684660694449673826205271902766363026345759436852747743967254218765160248630402258125202844303276381357264903281385470521070161164325276902001627351570675438339067652784355957225763207341000628151024518554862922220201109512940053316358078220681816224518400117972877854801506805929902506832781106133167532327833813179558969694268634413548545525533605595649634856393268111552838570383386406869870266457914799472663817890880697043874427042958587244568923338441053981863674366842769379075373006984522023718553749977766836594738859315852333132093474709715377682153430675891
d0=8429433927120666131169351623736961178529851960373209550653840828920672665447032524933438956407503522388445988812739437427277858013428300926608147855795349674824173869269407061090165202002106353884034590344852857623737262477675587193006629765892565228448265429521617733861051151345083787592170864896543517637252788111

d = 0
for k in range(0,e):
    print k
    X = var('X')
    results = solve_mod([e*d0*X - k*(n*X-X*X-n+X) == X], 2**1050)
    for x in results:
        p0 = ZZ(x[0])
        if is_prime(p0) and gcd(n,p0)!=1:
            print p0
            q0 = n//p0
            phi=(q0-1)*(p0-1)
            d = inverse_mod(e,phi)
            break
    if(d!=0):
        break
print d
m = pow(c,d,n)
print m

其他题目

除此以外，印象中还存在另外一些coppersmith题目，印象中我把所有解方程有关的题目都当成coppersmith了。我新人赛的时候也心血来潮自创了一题，打算放到校赛用。反正最基础的办法就是：找齐足够的方程，代入消元求解。

Related post
Comment
Share
To Top
  • 极光实验室战队考核密码学部分考察点与题解

    四月 1日, 2020

    关键词：DH密钥交换协议，Coppersmith攻击，混合密码通信，rsa及aes编程。 题目 出题思路由于是战队考核，这次的题目应出得相对综合，也更考验同学们的知识面和对各方面加密的理解和把握能力。同时，题目应当结合密码学的实际应用...

    极光实验室战队考核密码学部分考察点与题解
  • ACTF新人赛密码学部分考察点与题解

    二月 16日, 2020

    关键词：密码学，CTF出题，题解。 具体的题目，考点，题解请见项目链接。 新生赛是我进入实验室以来参与出题的第一场比赛。为了这个比赛，我在平时还是做了一些积累，只有有灵感，我就着手开始写出题脚本和解题脚本，然后有一道自己完成不了的题目...

    ACTF新人赛密码学部分考察点与题解
  • 螺旋上升，这就是我期盼的人生

    一月 16日, 2021

        还记得高中的时候，在政治课上学过一个“螺旋上升”理论，即“事物的发展，总是螺旋上升的”，而列宁也说过， “发展似乎是在重复以往的阶段，但它是以另一种方式重复，是在更高的基础上重复。” 回顾我这21年...

    螺旋上升，这就是我期盼的人生
  • 致即将逝去的21岁

    一月 16日, 2021

        在即将迎来22岁的日子，我想回顾一下21岁时的一些收获与遗憾。也当是把元旦没写完的文案补上一下。     在6岁的时候，我在爷爷家曾经画过一幅画，爷爷问我在画什么，我说，...

    致即将逝去的21岁
  • ACTF2020密码学部分writeup

    六月 5日, 2020

    编写的项目文件请参考项目链接。同时欢迎大家访问ACTF2020的所有赛题。喜欢的话请多多资瓷一下，给我们实验室的项目加个Star或者Fork，谢谢。 为了保护服务器的同时不给选手带来更多困难，密码学部分的交互题开了pow算力检测，我也...

    ACTF2020密码学部分writeup
  • GPT技术初探

    五月 27日, 2020

    第一部分 引入1.概念GPT：Generative Pre-Training 生成式的预训练、 2.工作机制GPT也采用两阶段过程，第 一个阶段是利用语言模型进行预训练，第二阶段通过 Fine-tuning的模式解决下游任务。 3.G...

    GPT技术初探
  • 通过python脚本自动插入汇编反调试代码

    五月 20日, 2020

    研究背景在之前OLLVM项目的研究过程中，我们发现反调试技术对反混淆脚本有一定的干扰作用，如果可以在OLLVM的中间代码中自动化插入反调试代码，那么就可以给OLLVM的代码混淆增加一层保障。 方案分析探讨多种方案以后，我认为最适合在汇...

    通过python脚本自动插入汇编反调试代码
  • 答辩顺序抽签小程序

    五月 14日, 2020

    最近比较喜欢动手编写小程序和脚本。晚上有同学和我讨论对答辩队伍进行公平抽签的方案，所以打算编写一个很简单的小脚本，并做到尽量减少计算量。 脚本思路按照一定根据给各个队伍排序，然后初始化抽签序号池，每次随机获取池内的一个值，交给其中一支...

    答辩顺序抽签小程序
  • 课堂记录小助手

    五月 7日, 2020

    作为一名课代表，我需要每天记录同学在QQ群的签到和回答问题情况。开始我是直接把记录复制到word里面手动提取有用的消息，最后我决定解放双手编写一个自动化处理脚本。 这个脚本需要一些什么功能呢？1.最基础的，就是从漫长的聊天记录中提取专...

    课堂记录小助手
  • 基于门限方案的条形码保密及容错技术

    四月 30日, 2020

    关键词：门限方案，条形码保密，条形码容错，条形码认证与防伪造。 经历过初期两个小项目的探索，我们项目团队积累了一定的项目研究经验，在老师和16级学长的帮助下，我们把研究方向转到了门限方案的实际应用上。结合市面上用9张合并的条形码提高条...

    基于门限方案的条形码保密及容错技术
Please check the parameter of comment in config.yml of hexo-theme-Annie!
ESC