Cryptography Reference
In-Depth Information
g := igcd(q-1, e)
end do;
n := p*q;
d := eˆ(-1) mod (p-1)*(q-1);
igcdex(p, q, 'pinv', 'qinv');
key := [[n, e], [n, d, p, q, d mod (p-1), d mod (q-1), pinv mod q, qinv mod p]];
if format = hex then
StringTools:-LowerCase
∼∼
convert
∼∼
(key, hex))
elif format = decimal then
key
else
error "Unrecognized key format"
end if;
end proc:
Example 8.2
Let us use the preceding function to generate a 2048-bit RSA key.
When we speak of a
t
-bit RSA key,
t
is the bit length of the modulus, so the key we
are about to generate will have a 2048-bit modulus and we will take
k
=
1024 as the
value of the security parameter when calling
RSAKeyGen
. Since the output is very
long, we will not print it entirely but will only print the essential parts of the public
key and the private key:
> rsakey := RSAKeyGen(1024, 618020429552270915383892324472348012175,
410275671464698780248543572127557803186):
> pk := rsakey[1];
["d5ad715cdbbcf4d61a6cf85e7d7e20d09c5ad2683167454a0bdc67dd86b4401efbf9349b915f6e\
2036bf9791f84df90e36f8c070fb3cd12a72c30dc04fcca208663ba7f2027af7edd6a9481d2ea84f\
97213da2a78def50b50b059da1d3f5888b5708dcfeb7544a1526c4f334adb3db971f043d78bffc65\
b7287ac31b5cfd810eb00f0697f8f75de30fd4ccd454ed0bc83cb06c98a6353a4f9b95b976ffb850\
1879c77e50f121c26b6283cb10efac52d71453877948b387224522110fff795412d6cd38fc866f0f\
36b708c16a27cb9576cd7194f1526c93414f1a89ef97417dccee2f048076c64c8397214283738764\
8257b7f959d82cfd5bf47ed18ebc4ec245", "10001"]
We check the length:
> StringTools:-Length
∼
(pk);
[512, 5]
We see that the hexadecimal length of themodulus is 512—which, bearing inmind
that the most significant digit is hexadecimal
d
, corresponds to a 2048-bit modulus.
The encryption exponent is
"10001"
in hex which corresponds to the default value
2
16
1. The decryption exponent, on the other hand, is the following:
> sk := rsakey[2]: sk[2];
"5b8d64f5147171b60abc85ee76768438ddc54c41b8693716f2de0ce2adc4ad749921bd98aa40e93e8\
436b30aa809409d0690ae63ba41e49cfb6ef7855eab9f015a4c55392c36e3e3d405d4102cdd90bc8\
051984f9250e793aa954d64f91c4ad4e905b32ab0023d7bb290d063d1c92e5d21bcff59ad68c76c2\
2bbf6bcd2ab0b902530d5c67c2e1bffa74cd00282d31e765b61e9502b96c6aa6de0c5f4897f2e3db\
84ea8d247186f557b891827d587ac5a107615079bc151059275dc4e4c24ce15fee1fad5c2744aa8c\
ef878117313782e08dc705c4aae4d2867f5e915b07eb5a3eebccfc5497fd9925eefaec2985de5f8e\
26b2515a327bc99effb9bf878446441"
+
Exercise 8.8
Include in the function
RSAKeyGen
an additional check to ensure
that the primes
p
and
q
that it generates are not too close, so that the modulus cannot
be factored by Fermat's method. This is largely unnecessary when generating keys
of realistic size but may serve to exclude extreme cases, such as the primes being
equal, when generating very small 'toy examples'. Of course, these toy examples
might also be banned altogether by including in the function an instruction requiring
a minimum value for
k
.
