Coppersmith Method – RSA



When we study about RSA cracking, we could hear a lot about the Coppersmith Method. Briefly, when we want to get some roots against the polynomial, we can compute it simply (not simple to me, simple to computer lol). But if the polynomial is on modulus field, it changes into a completely different problem. So the Coppersmith Method is the innovation itself XD

Coppersmith Method

Let’s think about a simple polynomial $x^2 + x + 1 = 0$. We can calculate the roots about this polynomial, it is simple enough to calculate (for me too lol). But when we think about the same polynomial with a modulus field appended, like $x^2 + x + 1 \equiv 0 \pmod{123456789}$. Can u?


In the previous description, compared to the equation with modulus, the equation without modulus is relatively very easy to solve. Copersmith also devised the Copersmith method based on the method of eliminating modulus from equations in which modulus exists.
$$C \equiv M^e \pmod{n}$$
Above is the encryption process used in a typical RSA equation. As intended, the factorization of N is impossible in time issue, so N cannot be easily recovered.

But, what about this condition $ M < n^{\frac{1}{e}}$ added? The modulus field will be unused, so we can just calculate on integer field. This is the basic idea of coppersmith method.

let me think about the equation $f(x) \equiv 0 \pmod{a}$. If there is some $x_0$ which matches $|f(x_0)| < a$, we can remove the modulus as the previous example. Too trivial, but it is hard to get some $x_0$ which satisfies this condition. So coppersmith will change this into a condition based on $x$ not $f(x)$.

Howgrave-Graham Theorem

This theorem converts $f(x) \equiv 0 \pmod{a}$ to $f(x) = 0$. Let me define some things below.

  1. The vector made of coefficients from function $f$ called coefficient vector. Can be expressed as $[a_0, a_1, \cdots, a_n]$
  2. The norm of function $f$ is the norm of coefficient vector. Can be expressed as $||f||^2 = \sum{{a_i}^2}$

Now, we can talk about the conditions in this theorem.

  1. For some $X$, every var which matches $|x_0| < X$ also matches $f(x_0) \equiv 0 \pmod{a}$

“Coppersmith Method – RSA”에 대한 5개의 응답

  1. sklep online 아바타

    Wow, superb weblog structure! How long have you ever been blogging for?

    you make blogging glance easy. The full glance of your site is great, as
    well as the content material! You can see similar here e-commerce

  2. Odkryj jak 아바타

    Excellent write-up

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다