LOV3

生成时形如如下式子生成的密钥都有会受到ROCA攻击(CVE-2017-15361)

$p = k \times M + (65537 ^ a \mod M)$

去Gitlab clone下 ROCA 攻击的源码 (neca)

接着 cd 进入刚刚 clone 项目的目录进行类似下面的操作

lov3@txt:~/tools/Crypto/neca$ ls
CMakeLists.txt  LICENSE  README  build  cmake  src
lov3@txt:~/tools/Crypto/neca$ rm build/
rm: cannot remove 'build/': Is a directory
lov3@txt:~/tools/Crypto/neca$ rm -rf build/
lov3@txt:~/tools/Crypto/neca$ ls
CMakeLists.txt  LICENSE  README  cmake  src
lov3@txt:~/tools/Crypto/neca$ mkdir build
lov3@txt:~/tools/Crypto/neca$ cd build/
lov3@txt:~/tools/Crypto/neca/build$ cmake ..
-- The C compiler identification is GNU 11.3.0
-- The CXX compiler identification is GNU 11.3.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found GMP: /usr/lib/aarch64-linux-gnu/libgmp.so  
-- Found OpenMP_C: -fopenmp (found version "4.5") 
-- Found OpenMP_CXX: -fopenmp (found version "4.5") 
-- Found OpenMP: TRUE (found version "4.5")  
-- Configuring done
-- Generating done
-- Build files have been written to: /home/lov3/tools/Crypto/neca/build
lov3@txt:~/tools/Crypto/neca/build$ ls
CMakeCache.txt  CMakeFiles  Makefile  cmake_install.cmake
lov3@txt:~/tools/Crypto/neca/build$ make
[ 50%] Building CXX object CMakeFiles/neca.dir/src/main.cpp.o
[100%] Linking CXX executable neca
[100%] Built target neca
lov3@txt:~/tools/Crypto/neca/build$ ls
CMakeCache.txt  CMakeFiles  Makefile  cmake_install.cmake  neca
lov3@txt:~/tools/Crypto/neca/build$ ./neca 
NECA - Not Even Coppersmith's Attack
ROCA weak RSA key attack by Jannis Harder (me@jix.one)

 *** Currently only 512-bit keys are supported ***

 *** OpenMP support enabled ***

Usage: neca <N>
lov3@txt:~/tools/Crypto/neca/build$

工具安装完成，用这道题(BattleCTF-rockyou) 试试工具

from Crypto.Util.number import bytes_to_long
FLAG = bytes_to_long(open("flag.txt").read().encode())
n = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101 
e = 65537 
c = pow(FLAG, e, n) 
print(f"c = {c}") 
# c = 10924637845512114669339598787759482373871484619074241479073765261738618851409833137908272858354441670603598700617114497065118363300675413269144392865493504

**lov3@txt**:**~/tools/Crypto/neca/build**$ ./neca 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101

NECA - Not Even Coppersmith's Attack

ROCA weak RSA key attack by Jannis Harder (me@jix.one)

  

 *** Currently only 512-bit keys are supported ***

  

 *** OpenMP support enabled ***

  

N = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101

Factoring...

  

 [===============         ] 62.14% elapsed: 175s left: 106.63s total: 281.64s

  

Factorization found:

N = 127801155916875524149457561567678575565270601000365665873572024750823913157383 * 113917064871970833547038329106470040388258358281464605006613652518914797349747

拿到p，q 写个程序解出m

q = 127801155916875524149457561567678575565270601000365665873572024750823913157383
p = 113917064871970833547038329106470040388258358281464605006613652518914797349747
c = 10924637845512114669339598787759482373871484619074241479073765261738618851409833137908272858354441670603598700617114497065118363300675413269144392865493504
e = 65537
n = p * q
d = inverse_mod(e, (p - 1) * (q - 1))
pt = pow(c, d, n)
from Crypto.Util.number import long_to_bytes    
print(long_to_bytes(pt))
# Output:
# b'battleCTF{ROCA_shork_me_0x0x0x}\n'

solve~

存一下sage解ROCA的代码

fllename: sage_functions.py

#sage_functions.py
from sage.all_cmdline import *
 
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    """
    Taken from https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/coppersmith.sage
    Coppersmith revisited by Howgrave-Graham
    finds a solution if:
    * b|modulus, b >= modulus^beta , 0 < beta <= 1
    * |x| < XX
    More tunable than sage's builtin coppersmith method, pol.small_roots()
    """
    #
    # 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)
    """
    #
    # 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]
 
    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()
 
    # 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

替换入自己的 $n$

fllename: ROCA_attack.py

from sage.all import *
from tqdm import tqdm
 
 
def solve(M, n, a, m):
    # I need to import it in the function otherwise multiprocessing doesn't find it in its context
    from sage_functions import coppersmith_howgrave_univariate
 
    base = int(65537)
    # the known part of p: 65537^a * M^-1 (mod N)
    known = int(pow(base, a, M) * inverse_mod(M, n))
    # Create the polynom f(x)
    F = PolynomialRing(Zmod(n), implementation='NTL', names=('x',))
    (x,) = F._first_ngens(1)
    pol = x + known
    beta = 0.1
    t = m+1
    # Upper bound for the small root x0
    XX = floor(2 * n**0.5 / M)
    # Find a small root (x0 = k) using Coppersmith's algorithm
    roots = coppersmith_howgrave_univariate(pol, n, beta, m, t, XX)
    # There will be no roots for an incorrect guess of a.
    for k in roots:
        # reconstruct p from the recovered k
        p = int(k*M + pow(base, a, M))
        if n%p == 0:
            return p, n//p
 
def roca(n):
 
    keySize = n.bit_length()
 
    if keySize <= 960:
        M_prime = 0x1b3e6c9433a7735fa5fc479ffe4027e13bea
        m = 5
 
    elif 992 <= keySize <= 1952:
        M_prime = 0x24683144f41188c2b1d6a217f81f12888e4e6513c43f3f60e72af8bd9728807483425d1e
        m = 4
        print("Have you several days/months to spend on this ?")
 
    elif 1984 <= keySize <= 3936:
        M_prime = 0x16928dc3e47b44daf289a60e80e1fc6bd7648d7ef60d1890f3e0a9455efe0abdb7a748131413cebd2e36a76a355c1b664be462e115ac330f9c13344f8f3d1034a02c23396e6
        m = 7
        print("You'll change computer before this scripts ends...")
 
    elif 3968 <= keySize <= 4096:
        print("Just no.")
        return None
 
    else:
        print("Invalid key size: {}".format(keySize))
        return None
 
    a3 = Zmod(M_prime)(n).log(65537)
    order = Zmod(M_prime)(65537).multiplicative_order()
    inf = a3 // 2
    sup = (a3 + order) // 2
 
    # Search 10 000 values at a time, using multiprocess
    # too big chunks is slower, too small chunks also
    chunk_size = 10000
    for inf_a in tqdm(range(inf, sup, chunk_size)):
        # create an array with the parameter for the solve function
        inputs = [((M_prime, n, a, m), {}) for a in range(inf_a, inf_a+chunk_size)]
        # the sage builtin multiprocessing stuff
        from sage.parallel.multiprocessing_sage import parallel_iter
        from multiprocessing import cpu_count
 
        for k, val in parallel_iter(cpu_count(), solve, inputs):
            if val:
                p = val[0]
                q = val[1]
                print("found factorization:\np={}\nq={}".format(p, q))
                return val
 
if __name__ == "__main__":
    # Normal values
    #p = 88311034938730298582578660387891056695070863074513276159180199367175300923113
    #q = 122706669547814628745942441166902931145718723658826773278715872626636030375109
    #a = 551658, interval = [475706, 1076306]
    # won't find if beta=0.5
    # p = 80688738291820833650844741016523373313635060001251156496219948915457811770063
    # q = 69288134094572876629045028069371975574660226148748274586674507084213286357069
    # #a = 176170, interval = [171312, 771912]
    # n = p*q
    n = 14558732569295568217680262946946350946269492093750369718350618000766298342508431492935822827678025952146979183716519987777790434353113812051439651306232101
    # For the test values chosen, a is quite close to the minimal value so the search is not too long
    roca(n)

利用 两个代码放在同一个目录下，被引用的代码名必须为 sage_functions.py

sage ROCA_attack.py

即可得到 $p, q$

但是 ARM macOS make 的时候就会出现很多问题, 如下, 有大佬看见知道怎么就觉请评论告知

lov3@Cryptoer ~/D/C/T/n/build> cmake --build .                                                                   master!

[ 50%] Building CXX object CMakeFiles/neca.dir/src/main.cpp.o
clang: warning: argument unused during compilation: '-Xclang -fopenmp -I/opt/homebrew/Cellar/libomp/16.0.6/include' [-Wunused-command-line-argument]
In file included from /Users/lov3/Documents/Code/Tools/neca/src/main.cpp:12:
/Users/lov3/Documents/Code/Tools/neca/src/arith.h:28:24: error: cannot initialize a variable of type 'const ulimb_t *' (aka 'const unsigned long long *') with an rvalue of type 'mp_srcptr' (aka 'const unsigned long *')
        ulimb_t const *value_limbs = mpz_limbs_read(value.get_mpz_t());
                       ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/lov3/Documents/Code/Tools/neca/src/arith.h:59:18: error: cannot initialize a variable of type 'ulimb_t *' (aka 'unsigned long long *') with an rvalue of type 'mp_ptr' (aka 'unsigned long *')
        ulimb_t *value_limbs = mpz_limbs_write(value.get_mpz_t(), W);
                 ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
2 errors generated.
make[2]: *** [CMakeFiles/neca.dir/src/main.cpp.o] Error 1
make[1]: *** [CMakeFiles/neca.dir/all] Error 2
make: *** [all] Error 2
lov3@Cryptoer ~/D/C/T/n/build>                                                                                 2 master!