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

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

发表于: 2021-3-19 13:45 10562

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

fishmouse

2021-3-19 13:45

10562

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

问题变为如何找到$x$

Coppersmith解决了这个问题，更多可参考：Comppersmith

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

依据msg.txt，知道

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

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

故有以下已知信息：

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

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

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

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

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

代码实现：

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

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

sage脚本运行结果：

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

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

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

N = 13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649

e = 3

c = 6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493
# m&x

m_x = 947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724
 
x = 15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740

N =

13876129555781460073002089038351520612247655754841714940325194761154811715694900213267064079029042442997358889794972854389557630367771777876508793474170741947269348292776484727853353467216624504502363412563718921205109890927597601496686803975210884730367005708579251258930365320553408690272909557812147058458101934416094961654819292033675534518433169541534918719715858981571188058387655828559632455020249603990658414972550914448303438265789951615868454921813881331283621117678174520240951067354671343645161030847894042795249824975975123293970250188757622530156083354425897120362794296499989540418235408089516991225649

e = 3

c =

6581985633799906892057438125576915919729685289065773835188688336898671475090397283236146369846971577536055404744552000913009436345090659234890289251210725630126240983696894267667325908895755610921151796076651419491871249815427670907081328324660532079703528042745484899868019846050803531065674821086527587813490634542863407667629281865859168224431930971680966013847327545587494254199639534463557869211251870726331441006052480498353072578366929904335644501242811360758566122007864009155945266316460389696089058959764212987491632905588143831831973272715981653196928234595155023233235134284082645872266135170511490429493

# m&x

m_x =

947571396785487533546146461810836349016633316292485079213681708490477178328756478620234135446017364353903883460574081324427546739724

x =

15581107453382746363421172426030468550126181195076252322042322859748260918197659408344673747013982937921433767135271108413165955808652424700637809308565928462367274272294975755415573706749109706624868830430686443947948537923430882747239965780990192617072654390726447304728671150888061906213977961981340995242772304458476566590730032592047868074968609272272687908019911741096824092090512588043445300077973100189180460193467125092550001098696240395535375456357081981657552860000358049631730893603020057137233513015505547751597823505590900290756694837641762534009330797696018713622218806608741753325137365900124739257740

#简单统计一下，m&x和x的位数

len(bin(m_x)[2:]),len(bin(x)[2:])

#简单统计一下，m&x和x的位数

len(bin(m_x)[2:]),len(bin(x)[2:])

# x比m多的位数

2048-440

# x比m多的位数

2048-440

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)

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)

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

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