Cryptography Reference
In-Depth Information
> phi_n :=
23538372498408898020904820516194882190870515954482550253711433294824967383591284\
46844042074690277603497784339917211555362254378971172185266564969960989190738145\
81559762081612973350421474680153315264623295830664463318924022191113778607540232\
32012364526054251283789295120489864731342782075372824073611435656184337866561951\
92613311184636896350127529563714037782012413506872669940929569445028376002383803\
42909677080585685745264747605181667394509971522811194316486938945937669639819167\
47306930850182227083585541238788152551097191631224444591869259495359048189272580\
669145965551624035183715655749747482032334978351370258132:
These data are enough to factor
n
quickly. We compute the coefficients of the
equation
x
2
−
bx
+
c
=
0 that we must solve:
> b := n-phi_n+1:
c:=n:
Finally we useMaple to solve this equation, which is done almost instantaneously:
> facts := solve(xˆ2-b*x+c = 0, x);
1673947868545165086637324620110773919578289106919415262741749456019641771187612182\
38587947183288524849313248383999562517418239392666913387808271404151449589166653\
62808917235581393766785161968921729240793583128217343452625476701711431946085971\
7651759465021160602915439915134864901607483156505786734310651214703, 14061592323\
58065814243220638114914727006962514010387483674614829954740574534738376963342763\
32195946330433502515206855455106156801458748810827825070173818337856303177524639\
66236071138923924016262790382557799093883638249953959675942202064893975790513598\
3807040126726524324650583779343344737588425290389532628967
We check that
n
is indeed the product of these integers (it may be also checked
that they are prime):
> evalb(n = mul(i, i = facts));
true
We stress that, while factoring this 2048-bit modulus
n
was very easy knowing
φ(
, it is currently infeasible to factor it on input
n
alone, even with the most
powerful resources available. To put it in perspective we recall that the current record
factorization of an RSA modulus like this one corresponds to a 768-bit number
an extrapolation using the complexity of NFS indicates that the factorization of a
2048-bit modulus with the same resources would take more than 10
12
years.
n
)
Exercise 8.3
Use the function
PseudoRandomPrime
to generate two 2048-bit
primes
p
and
q
. Compute the modulus
n
=
pq
and
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
and
discard
p
and
q
. Use the values of
n
and
φ(
n
)
to factor
n
.
The previous attempt to break the RSA assumption without being able to factor
the modulus
n
was not successful because, although we can easily invert the RSA
function once we know
φ(
n
)
, this knowledge also allows us to factor
n
. But we do not
really need to know
φ(
n
)
to invert the RSA function for it is clear that knowing the
Z
φ(
n
)
inverse
d
of
e
in
is enough. So we may also ask: is there any way of computing
d
that is easier than factoring
n
?
The answer is, again, no; if we can efficiently compute
d
from
n
and
e
, then we
can also efficiently factor the modulus
n
. Indeed, there is a PPT Las Vegas algorithm
due to Miller that, on input
∈ Z
n
produces the factorization
(
,
,
)
n
e
d
and a random
x
of
n
with probability at least 1
2 (see [140, 8.2.2]). In fact, this problem has also
been solved deterministically by Coron and May [55], who found a deterministic
/