3
$\begingroup$
from Crypto.Util.number import *
from flag import flag

def gen_prime(nbit):
    while True:
        p = 0
        for i in range(nbit, nbit>>1, -1):
            p += getRandomRange(0, 2) * 2 ** i
        p += getRandomNBitInteger(nbit>>3)
        if isPrime(p):
            return p

nbit = 512
p, q, r = [gen_prime(nbit) for _ in '012']
e, n = 65537, p * q * r

m = bytes_to_long(flag)
c = pow(m, e, n)

print(f'n = {n}')
print(f'c = {c}')

"""
n = 306274031191812861390142322943384171567281235901023281150152366709090671749498337889684025397615153433878170972936066715221203963189667691979936604050835848397126937722483985215998814393176118687506861486835225543585451024226910726976901506973151291379128731667011697266671380831373270759872483773774444157994113393807135699243427889953159841567700099682080305355884531709396908787777504205775972655070971179462480070831508541674970198913788578939945648909705829
c = 223849092404967389418032074311452301651293919558152640065438289744845837981617978133447578227300156302182335073619698990940597295177229704048168320777498240448811390343120956888620737076325442001666883042713739861144512318389043548008886406065462992332747911568586879243279225955299270912019379515768839390586943094509691563525269138915388095236050068130199760650753758898265542401663546938899693685809537450793106770047460151231224343501919710408682427560812073
"""

I am very curious if this is even solvable, the author refuses to provide a writeup, the best progress made was finding the lower half bits of each factor, but if you want to use coppersmith then you need to know 2/3 of the bits which leaves 90 bits to bruteforce which is unfeasible...

any other ideas to factor n?

$\endgroup$

3 Answers 3

2
$\begingroup$

That sounds like a fun challenge. Let us look at what this code snippet is doing.

While it hasn't found a prime number p, it will go from $i = 512$ to $i = 256$ and add $2^{i}$ to the value 0 randomly with 50% chance (getRandomRange(0, 2) is either 0 or 1).

This means that it is generating a number whose bits from 512 to 256 are properly random.

Next it will pick a random nbits>>3 bit integer, but ngits>>3 $= 64$ when nbits $= 512$. So it picks a 64 bits integer and adds it that number with random 512 to 256 bits values...

In the end it means we have number whose first 256 bits are properly random and whose last 64 bits are properly random. But the bits from 256 to 64 are all zeroes, so we know already 192 bits.

You can see this by printing the value using print(bin(p)) when running the code. The resulting numbers will look like these (notice all the 0s on the second half?):

0b111000010001110101000011010000111110101010001011110111111100011110110000011101100111011000111110111010110010100110010101011011011001110011011111010001010011000111001001101111001000000101110011110110100001111100110100001100100110110001100010100101110010000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001110101000111010110001001001001011100101010000111000111101000001
0b100011111101100000001111100000111010000101101011110000110110001001110101010111010010010011001001111110110101010011010110111110110100111010010011101111110011100101000001101110100101010000011111111010110001001010100001101101111010100011010100000010110100101000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001101111000110100011100110010110111110011011010101010100010011
0b11110101000101110011000100110000011111001000000111110101011111110101101100011000000011011011111110001100111110111010000111110110010101010100001100001100000101010101010010110011100011101010010010100101110110011001010110111010111101110001111111000111111111100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001111010011111010100100101001111110011000010010101110010011001

So the gist of the problem is: when faced with neither known least significant bits (LSB) nor known most significant bits (MSB), but known middle bits (MID) prime integers, can we leverage Coppersmith to factor $N$?

The response is that no, not directly! But we can probably use the same idea.

At the end of the day, I am not sure which solution is simpler, but to solve this challenge I think you need to implement what is described in that paper, in section 4.2.4 and perform a LLL on your custom matrix, with the extra "twist" that you're working with 3 factors instead of 2. This looks like a possible way towards a solution.

There are two problems here, however.

  1. The first one is that you can't represent the partial information you have about the primes as an univariate polynomial $f(x)$. Instead you need to represent it using 2 variables: the unknown MSB and the unknown LSB. So instead your polynomial becomes: $f(x,y) = x \cdot 2^{256} + y$, for $x < 2^{256}$ and $y<2^{64}$ and you need to solve for both $x$ and $y$. So you'll need to rely on a modified Howgrave-Graham / Coppersmith attack...

  2. The second one is that the Coppersmith methods usually work when we have partial information about a single prime, and it typically requires a certain amount of information, that I am not sure we have here. I'm not familiar with multiple factor RSA attacks, and Coppersmith, and I would need to research this a bit more, but I believe that you need to have only $r < n^\frac{1}{2}$ unknown bits (for $n$ the modulus size) for a Coppersmith based solution to work, and that is not the case here as we only know 192 bits per prime, times $3$ that's only 576 known bits out of 1536 bits, so we have ~960 unknown bits.

So these could indicate that Coppersmith might not help us here...

So, another option would be to take advantage of the redundancy of the information, and try and attack this using the "branch and prune" method as explained in section 4.3 of that same paper, but the tree would become larger since you have 3 factors and not just two.

I might look into trying to implement that latter option later this week, if I have some time, to confirm whether it works or not.

$\endgroup$
3
  • 2
    $\begingroup$ if you look at the factorisation of n % 2**(64*3) then you can find the 64-bit LSB of each prime: 9525340967214022543, 10128795423132424151, 11253238607042956333. Also I think the title could be a hint towards work of Richard E. Crandall $\endgroup$
    – akonzu
    Commented Nov 29, 2023 at 3:25
  • $\begingroup$ Ah that's a really good point. Factoring the lowest part of $n$ gives us $71 * 293 * 724037101 * 13989332051 * 540943066242511 * 9525340967214022543$ and there is only one way of getting 3 numbers of each 64 bits by picking factors from these. But I don't see yet any connections to Crandall but yeah that seems like a hint. $\endgroup$
    – Lery
    Commented Nov 29, 2023 at 14:20
  • $\begingroup$ FYI, I implemented the "branch and prune" attack against 3 primes RSA with known half of the bits, but it sadly didn't seem to run in a reasonable time since that means instead of having $2^\ell$ tail-recursive calls to solve, we have $4^\ell$ calls and it seems that's just too expensive here with $\ell = 256$ $\endgroup$
    – Lery
    Commented Dec 13, 2023 at 16:47
1
$\begingroup$

update: author said coppersmith bound overlooked for 3 vs 2 primes

so it's probably unsolvable

$\endgroup$
0
$\begingroup$

Actually still more information here.We know n can be written as n=(2^256x1+e1)(2^256x2+e2)(2^256x3+e3),by using some shifting skills we can get more about x1,x2,x3.For example we can easily get some high bits of product of x1x2x3,or some low bits of x1e2e3+x2e1e3+x3e1e2 etc.Once we know more bits of x1 ,x2 or x3 we can use coppersmith to factor n.

$\endgroup$
9
  • $\begingroup$ Maybe lattice can help with the first step $\endgroup$ Commented Dec 5, 2023 at 4:29
  • $\begingroup$ Actually the low 256 bits of (n>>256) are the low 256 bits of x1e2e3+x2e1e3+x3e1e2. $\endgroup$ Commented Dec 5, 2023 at 12:09
  • $\begingroup$ yes print(bin(n)[-512:-256]) print() print(bin(x1*e2*e3+x2*e1*e3+x3*e1*e2)[-256:]) $\endgroup$
    – akonzu
    Commented Dec 5, 2023 at 12:13
  • $\begingroup$ assert (x1*e2*e3+x2*e1*e3+x3*e1*e2) % 2**256 == int(bin(n)[-512:-256], 2) $\endgroup$
    – akonzu
    Commented Dec 5, 2023 at 12:14
  • $\begingroup$ yeah but I still don’t know how to use this hah.if we know more 100 bits of any x we can copper. $\endgroup$ Commented Dec 5, 2023 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.