首页
论坛
课程
招聘
[原创]Crpyto-RSA stereotyped message atack-(UCTF2021-a bit weird)
2021-3-19 13:45 5461

[原创]Crpyto-RSA stereotyped message atack-(UCTF2021-a bit weird)

2021-3-19 13:45
5461

前段时间做UCTF2021的Crypto题时,遇到的一道RSA stereotyped message攻击的题,主要涉及的知识有RSA 、Coppersmith、与 and或 or的理解、移位操作。由于公式原因,若感兴趣可参考本人博客:https://fishni.github.io/2021/03/17/Crypto-03-RSA%20Stereotyped%20message%20attack-(UCTF2021-a%20bit%20weird)/

场景

要传递的message格式:

 

hello ,my name is xxx

 

在使用RSA对这个message加密,我们知道密文ciphertext和公钥(N,e=3),如何求原始的message

攻击阐述

我们用b'\x00'替换消息中的x,这样就有了$(m+x)^e$ mod n=c

  • m 是用b'\x00'替换后的消息
  • x是xxx我们要发现的
  • (e,n)是公钥,c是密文

问题变为如何找到$x$

 

Coppersmith解决了这个问题,更多可参考:Comppersmith

攻击成功条件

  • e=3
  • $x<N^{\frac{1}{e}}$

UCTF2021-a bit weird

I found this weird RSA looking thing somewhere. Can you break it for me? I managed to find x for you, but I don't know how to solve it without d...

 

msg.txt

 

main.py

简要分析

  • 题目给出的挑战
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#main.py
from Crypto.Util import number
from secret import flag
import os
 
length = 2048
p, q = number.getPrime(length//2), number.getPrime(length//2)
N = p*q
e = 3
 
m = number.bytes_to_long(flag)
x = number.bytes_to_long(os.urandom(length//8))
 
c = pow(m|x, e, N)
print('N =', N);
print('e =', e);
print('c =', c);
print('m&x =', m&x);

依据msg.txt,知道

1
2
3
4
5
6
7
N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649
e = 3
c = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
# m&x
m_x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
 
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740

我们知道m&x,x但并恢复不了m,看来我们必须解密c才能得到$m | x$

1
2
#简单统计一下,m&x和x的位数
len(bin(m_x)[2:]),len(bin(x)[2:])
1
2
# x比m多的位数
2048-440

由此,可得知以下关于m|x

  • m&xxm为440位,x为2048位
  • 也就意味着m|x的高1608位对应x的高位

题解

故有以下已知信息:

  • a =m | x( 取低440位)
  • b =x(取x高1680位,低440位赋值为0)
  • 则 m | x==b+a,有$c==(b+a)^e mod N$

这可以归为RSA中stereotyped messages类型攻击,我们能使用Coppersmith恢复a

了解RSA-stereotyped messages

  • 使用场景:知道消息的部分关键位数,使用该方法可以找到消息的其他位

  • RSA的一个模型:$m^e=c (mod N)$,这个模型可以解决$c=(m+x)^e$,你知道明文的部分m,但是不知道x

    如果寻找的是消息的$N^{1/e}$,并且是个较小的根,应该可以较快找到

  • 多项式为$f(x)=(m+x)^e-c$ 想发现模N的一个根。

  • 代码实现:

1
2
3
4
5
6
7
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)

您可以使用这些值,直到它找到根。默认值应该是一个很好的开始。如果你想调整:

  • beta:在这种情况下总是1
  • XX是根节点的上界。未知数越大,XX也就越大。而且它越大……花的时间越多

sage脚本获取x(coppersmith.sage)

获取x的低440位的sage脚本,可在线运行sage脚本https://sagecell.sagemath.org/

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
# Coppersmith implementation
 
import time
 
debug = True
 
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)
 
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Coppersmith revisited by Howgrave-Graham
 
    finds a solution if:
    * b|modulus, b >= modulus^beta , 0 < beta <= 1
    * |x| < XX
    """
    #
    # init
    #
    dd = pol.degree()
    nn = dd * mm + tt
 
    #
    # checks
    #
    if not 0 < beta <= 1:
        raise ValueError("beta should belongs in (0, 1]")
 
    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")
 
    #
    # calculate bounds and display them
    #
    """
    * we want to find g(x) such that ||g(xX)|| <= b^m / sqrt(n)
    * we know LLL will give us a short vector v such that:
    ||v|| <= 2^((n - 1)/4) * det(L)^(1/n)
    * we will use that vector as a coefficient vector for our g(x)
 
    * so we want to satisfy:
    2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
 
    so we can obtain ||v|| < N^(beta*m) / sqrt(n) <= b^m / sqrt(n)
    (it's important to use N because we might not know b)
    """
    if debug:
        # t optimized?
        print("\n# Optimized t?\n")
        print("we want X^(n-1) < N^(beta*m) so that each vector is helpful")
        cond1 = RR(XX^(nn-1))
        print ("* X^(n-1) = ", cond1)
        cond2 = pow(modulus, beta*mm)
        print("* N^(beta*m) = ", cond2)
        print("* X^(n-1) < N^(beta*m) \n-> GOOD" if cond1 < cond2 else "* X^(n-1) >= N^(beta*m) \n-> NOT GOOD")
 
        # bound for X
        print("\n# X bound respected?\n")
        print("we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M")
        print("* X =", XX)
        cond2 = RR(modulus^(((2*beta*mm)/(nn-1)) - ((dd*mm*(mm+1))/(nn*(nn-1)))) / 2)
        print("* M =", cond2)
        print("* X <= M \n-> GOOD" if XX <= cond2 else "* X > M \n-> NOT GOOD")
 
        # solution possible?
        print("\n# Solutions possible?\n")
        detL = RR(modulus^(dd * mm * (mm + 1) / 2) * XX^(nn * (nn - 1) / 2))
        print("we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)")
        cond1 = RR(2^((nn - 1)/4) * detL^(1/nn))
        print("* 2^((n - 1)/4) * det(L)^(1/n) = ", cond1)
        cond2 = RR(modulus^(beta*mm) / sqrt(nn))
        print("* N^(beta*m) / sqrt(n) = ", cond2)
        print("* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n) \n-> SOLUTION WILL BE FOUND" if cond1 < cond2 else "* 2^((n - 1)/4) * det(L)^(1/n) >= N^(beta*m) / sqroot(n) \n-> NO SOLUTIONS MIGHT BE FOUND (but we never know)")
 
 
        # warning about X
        print("\n# Note that no solutions will be found _for sure_ if you don't respect:\n* |root| < X \n* b >= modulus^beta\n")
 
    #
    # Coppersmith revisited algo for univariate
    #
 
    # change ring of pol and x
    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()
 
    # compute polynomials
    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX)**jj * modulus**(mm - ii) * polZ(x * XX)**ii)
    for ii in range(tt):
        gg.append((x * XX)**ii * polZ(x * XX)**mm)
 
    # construct lattice B
    BB = Matrix(ZZ, nn)
 
    for ii in range(nn):
        for jj in range(ii+1):
            BB[ii, jj] = gg[ii][jj]
 
    # display basis matrix
    if debug:
        matrix_overview(BB, modulus^mm)
 
    # LLL
    BB = BB.LLL()
 
    # transform shortest vector in polynomial   
    new_pol = 0
    for ii in range(nn):
        new_pol += x**ii * BB[0, ii] / XX**ii
 
    # factor polynomial
    potential_roots = new_pol.roots()
    print("potential roots:", potential_roots)
 
    # test roots
    roots = []
    for root in potential_roots:
        if root[0].is_integer():
            result = polZ(ZZ(root[0]))
            if gcd(modulus, result) >= modulus^beta:
                roots.append(ZZ(root[0]))
 
    #
    return roots
 
# Public key
N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649
length_N = 2048
ZmodN = Zmod(N);
e = 3
 
# Obscuring term (was called `x` previously)
obs = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740
length_obs = 440
 
# Ciphertext
C = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
 
# Obsuring term with lower 440 bits zero'd (was called 'b' previously)
 
obs_clean = (obs >> length_obs) << length_obs
 
# Problem to equation.
# The `x` here was called `a` previously, which we are now solving for.
P.<x> = PolynomialRing(ZmodN)
pol = (obs_clean + x)^e - C
 
dd = pol.degree()
beta = 1                                # b = N
epsilon = beta / 7                      # <= beta / 7
mm = ceil(beta**2 / (dd * epsilon))     # optimized value
tt = floor(dd * mm * ((1/beta) - 1))    # optimized value
XX = ceil(N**((beta**2/dd) - epsilon))  # optimized value
 
# Coppersmith
roots = coppersmith_howgrave_univariate(pol, N, beta, mm, tt, XX)
 
print()
print("Solutions")
print("We found:", str(roots))

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# Optimized t?
 
we want X^(n-1) < N^(beta*m) so that each vector is helpful
* X^(n-1) =  7.64639144486953e938
* N^(beta*m) =  2671806721397343609369125721689846363846823887595317169259208269410807613515138193272735950395342600354585884618596837138454312445763723886601166952043062748009505139217794681937611360645445444140769994643446818754534866298130651329433014724715889837444867182984191620190905818803588933562722223328979700923934070485221893022649172511067198019458620445165662776678908770872500383557396520873649954695933963393304148547194098533517769688355801169062583949901346704912994207653877424119826970416572728246446525108981742453007188018279798743202379750534406784078069421672055702384012232185139872186089443647992149818358893834997950425662042050549158210414590239894415499371752895019920281114015215479652534190130397775610338712743962931327219145055957487978233015931879293485628652795746982880303598514651118264609343317354096189644231871614967872526120966984276731281546669197245726209804436508113354381914315232435894150854988195962920941429615473853382836785869279384612192426076678623082066854288934520774307146911493350318344271370346300740624871491708331236066262479670355346647414096649266862487754904950869424292066310431256633985253697575515680033391453124985988988670191902111914051233299493877035782843638962398086115700226338455677786300225885984533601124871244669214214105103887099092767042659106858007541232363169127153863660502490389037875332835859504268824420222360070871822883878805542227544448876610761790896706106782074035914998714448926799887557941643969590869586865208655191892111098282289241597413702345534627562696456765064323919706870792491286590311106687866963980133668858578681546024445557042142046310271577884977392878357234252136015344414426228232128893808200127782962118800708442012306882529157602730015548081294901794784475069861171020927127171831672885720955503939986515276832850113174993877171846111637519924505032034449
* X^(n-1) < N^(beta*m)
-> GOOD
 
# X bound respected?
 
we want X <= N^(((2*beta*m)/(n-1)) - ((delta*m*(m+1))/(n*(n-1)))) / 2 = M
* X = 2293147898964117288808008000805061598361990209625542167130389100774470198047923394475218668318195962237962277248056358
* M = 5.42671596118645e153
* X <= M
-> GOOD
 
# Solutions possible?
 
we can find a solution if 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
* 2^((n - 1)/4) * det(L)^(1/n) =  2.12973195403260e1702
* N^(beta*m) / sqrt(n) =  8.90602240465781e1847
* 2^((n - 1)/4) * det(L)^(1/n) < N^(beta*m) / sqrt(n)
-> SOLUTION WILL BE FOUND
 
# Note that no solutions will be found _for sure_ if you don't respect:
* |root| < X
* b >= modulus^beta
 
00 X 0 0 0 0 0 0 0 0 ~
01 0 X 0 0 0 0 0 0 0 ~
02 0 0 X 0 0 0 0 0 0 ~
03 X X X X 0 0 0 0 0
04 0 X X X X 0 0 0 0
05 0 0 X X X X 0 0 0
06 X X X X X X X 0 0
07 0 X X X X X X X 0
08 0 0 X X X X X X X
potential roots: [(2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029, 1)]
 
Solutions
We found: [2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029]

恢复明文m

  • 现在知道m|x的低440位,可恢复m
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
import libnum
 
def recover(x, m_and_x, m_or_x):
    ans = []
 
    while m_and_x > 0:
        a = x & 1 #取x的最低一位
        b = m_and_x & 1
        c = m_or_x & 1
 
        if a == 0: # 若a=0,0 and (0 或1)=0 故看 0 or c=c
            assert b == 0
            ans.append(str(c))
        else:     # 若a=1,则 1 or (1 or 0)=1 ,故看1 and b=b
            ans.append(str(b))
 
        # 都右移看下一位
        m_or_x >>= 1
        m_and_x >>= 1
        x >>= 1
 
    ans = ans[::-1]
    ans = "".join(ans)
    return libnum.n2s(int('0b'+ans,2))
m_or_x=2722393138562666557007231734043804673010965247853655886232567981247025605356740318867235245940388712958024648376448739432029199788029
# m_and_x为m|x低440位
m_and_x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740
m=recover(x,m_and_x,m_or_x)
print(m)
1
utflag{C0u1dNt_c0m3_uP_w1tH_A_Cl3veR_f1aG_b61a2defc55f}

参考链接

  • https://github.com/cscosu/ctf-writeups/tree/master/2021/utctf/A_Bit_Weird

  • https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage


【看雪培训】《Adroid高级研修班》2022年夏季班招生中!

最后于 2021-3-19 14:17 被fishmouse编辑 ,原因:
收藏
点赞2
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回