[原创]Crpyto-RSA stereotyped message atack-(UCTF2021-a bit weird)-CTF对抗-看雪论坛-安全社区|安全招聘|bbs.pediy.com

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

2021-3-19 13:45 5461

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

fishmouse

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

简要分析

题目给出的挑战

#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，知道

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&x和x知m为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的一个根。
代码实现：

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/

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脚本运行结果：

# 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

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)