前段时间做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$

#简单统计一下，m&x和x的位数
len(bin(m_x)[2:]),len(bin(x)[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/

# 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)

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