Try   HackMD

newcrypt

Description

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Solution

The script generated 4 numbers by:

for i in range(4): x = getPrime((1<<10)-random.randint(1<<0,1<<8)) y = inverse(x,(self.p-1)*(self.q-1)//GCD(self.p-1,self.q-1)) numbers.append(y)

The vulnerabililty here is that xs' bit length is small compared to n, so lattice-based attack could exploit it.

Howgrave-Graham and Seifert’s Attack had concluded that when given 4 public exponents whose private exponents' bit length is below

δ=0.441 times the bit length of n, it's likely to factorize n efficiently.

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

The bit length of x here is about

10241282048=0.4375.

The math

eidi=1+kiϕG

By this relation of e and d, we can have 10 basic equations: (

G is GCD and
s=nϕ
)

Wi:Geidikin=Gkis
Gi,j:kiGejdjkjGeidi=G(kikj)

The basic idea is using these equations to construct a vector-matrix equation

xB=v where
B
is an upper triangle matrix and

x=(k1k2k3k4,d1k2k3k4,k1d2k3k4,d1d2k3k4,k1k2d3k4,...,d1d2d3d4)

For the purpose that will be mentioned later, we want to choose

Gi,j as many as possible and
Wi
as less as possible.

My choice was:

k1k2k3k4=k1k2k3k4,k2k3k4W1,k3k4G1,2,k3k4W1W2,k2k4G1,3,k4W1G2,3,k4W2G1,3,k4W1W2W3,k2k3G1,4,k3W1G2,4,G1,2G3,4,W1W2G3,4G1,3G2,4,W1W3G2,4,W2W3G1,4,W1W2W3W4

This lead to:

    B=[ [1,-n,0,n^2,0,0,0,-n^3,0,0,0,0,0,0,0,n^4],
        [0,e1,-e1,-e1*n,-e1,0,e1*n,e1*n^2,-e1,0,0,0,0,0,-e1*n^2,-e1*n^3],
        [0,0,e2,-e2*n,0,e2*n,0,e2*n^2,0,e2*n,0,0,0,-e2*n^2,0,-e2*n^3],
        [0,0,0,e1*e2,0,-e1*e2,-e1*e2,-e1*e2*n,0,-e1*e2,0,0,e1*e2,e1*e2*n,e1*e2*n,e1*e2*n^2],
        [0,0,0,0,e3,-e3*n,-e3*n,e3*n^2,0,0,0,-e3*n^2,0,0,0,-e3*n^3],
        [0,0,0,0,0,e1*e3,0,-e1*e3*n,0,0,e1*e3,e1*e3*n,0,0,e1*e3*n,e1*e3*n^2],
        [0,0,0,0,0,0,e2*e3,-e2*e3*n,0,0,-e2*e3,e2*e3*n,-e2*e3,e2*e3*n,0,e2*e3*n^2],
        [0,0,0,0,0,0,0,e1*e2*e3,0,0,0,-e1*e2*e3,0,-e1*e2*e3,-e1*e2*e3,-e1*e2*e3*n],
        [0,0,0,0,0,0,0,0,e4,-e4*n,0,e4*n^2,0,e4*n^2,e4*n^2,-e4*n^3],
        [0,0,0,0,0,0,0,0,0,e1*e4,-e1*e4,-e1*e4*n,-e1*e4,-e1*e4*n,0,e1*e4*n^2],
        [0,0,0,0,0,0,0,0,0,0,e2*e4,-e2*e4*n,0,0,-e2*e4*n,e2*e4*n^2],
        [0,0,0,0,0,0,0,0,0,0,0,e1*e2*e4,0,0,0,-e1*e2*e4*n],
        [0,0,0,0,0,0,0,0,0,0,0,0,e3*e4,-e3*e4*n,-e3*e4*n,e3*e4*n^2],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,e1*e3*e4,0,-e1*e3*e4*n],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,e2*e3*e4,-e2*e3*e4*n],
        [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,e1*e2*e3*e4] ]

and

v=[k1k2k3k4, (1k1s)k2k3k4, (k1k2)k3k4, (1k1s)(1k2s)k3k4,        (k1k3)k2k4, (1k1s)(k2k3)k4, (k1k3)(1k2s)k4, Πi=13(1kis)k4,        (k1k4)k2k3, (1k1s)(k2k4)k3, (k1k2)(k3k4), (1k1s)(1k2s)(k3k4),        (k1k3)(k2k4), (1k1s)(1k3s)(k2k4), (1k2s)(1k3s)(k1k4), Πi=14(1kis)]

Every row of

B is a vector much bigger than
v
and
v
is linear combination of these rows.

To apply lattice attack, we still need

v to be balanced. Notice that
ein
,
dinδ
,
kinδ
,
sn0.5
, so
v
is dominated by the last component
Π(1kis)n2+4δ
.

Hence we need to multiply both

B and
v
by a diagonal matrix
D

diagonal_matrix([n^2,n^1.5,n^(2+delta),n,n^(2+delta),
                 n^(1.5+delta),n^(1.5+delta),n^0.5,
                 n^(2+delta),n^(1.5+delta),n^(2+2*delta),n^(1+delta),
                 n^(2+2*delta),n^(1+delta),n^(1+delta),1])

Now we can apply LLL algorithm to obtain

v and
x
, then calculate
ϕ=e1×d1k2k3k4k1k2k3k4
. If
ϕ
is calculated correctly, the roots of
x2(n+1ϕ)x+n=0
will be p and q consequently.

The only thing left is that we don't know the GCD of

p1 and
q1
, it could be any even number. Hence for every possible
G
, we need to multiply
e
by
G
first. It turned out that the GCD is just
2
though.

Reason why not choose
Wi
but
Gi,j

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Using the theorem, to increase the success rate of the attack, we need the volume of

B to be as large as possible. It means large components of
D
, which means small right hand side of each equation we choose.

By some observation, all the right hand side of the equations consists of

k1,k2,k3,k4.

When choosing

Gi,j, we elimintae
ki
and
kj
but only multiply the number by
(kikj)
. On the other hand, choosing
Wi
multiplies the number by
kis
, which is much larger.

We can even calculate the upperbound of bit length of

di by the theorem.

||v||n2+4δn116(32+13δ+22.5)4(e18e28e38e48n13δ+22.5)116=nvol(B)1nδ1534=0.441...

The script