Now, the SSH authentication key (public key / private key) for conscious people is still ed25519, but with RSA, what! ** The public key including your favorite character string is ** I can make it!
That's right, the biggest advantage of RSA was ** you can customize your own key including your favorite strings **! So, this article is about revisiting the appeal of RSA. (It's a lie)
TL;DR;
I made a material tool (Ruby script) that can embed your favorite character string in the public key! ※ https://github.com/angel-p57/qiita-sample/blob/master/rsa/rsa-genmykey.rb
RSA allows you to control the range of values for the main public key parameter $ n $, which in turn can lead to string embedding!
The RSA key data is determined by the private key parameters $ p, q $ (two giant prime numbers), but by narrowing the range of $ q $ according to the randomly created $ p $, the product $ n Control the range of = pq $!
Note: I don't think that "embedding your favorite character string" will lead to key vulnerability, but I can't take responsibility for anything, so please use it as a ** material **.
+/
. (That is, base64 character type)Below is an example of when I actually made it and tried it.
ruby rsa-genmykey.rb embedded character string> save destination file name
.ssh-keygen -y -f private key file> save destination file name
.ssh-copy-id
and confirmed that it can be used for public key authentication.The public key data created this time is ssh-rsa AAAAB3NzaC1yc2EAAAAADAQABAAACAQDF / angelp57 / a + cat + of + Flanders /…
, but except for the leading ssh-rsa
, the binary as shown in the following figure (partial) It is a character string converted from text) to base64.
Among them, the embedded character string / angelp57 / a + cat + of + Flanders /
is determined by the highest of the huge integer parameter $ n $ (
n = 0xc5fde9e07a5a79eff6be71ab7e… ). High-order digit excluding c5
.
Conversely, if you can narrow down the ** parameter $ n $ to a certain size range **, you can embed your favorite string.
Now, in the case of RSA, there are some key parameters (both integers).
For details, see Numerical Structure of Public Key Cryptography RSA.
Private key
Prime numbers $ p $ (prime1), $ q $ (prime2)
Index $ d $ (privateExponent)
Derived parameters $ d_p $ (exponent1), $ d_q $ (exponent2), $ q_ {inv} $ (coefficient)
Public key
Product $ n $ (Modulus)
Index $ e $ (publicExponent)
Of these, $ e $ is currently generally fixed at 65537 (0x10001), and all other parameters, including $ n = pq $, are determined by the prime numbers $ p, q $. In other words, how to decide ** $ n $ comes down to the story of how to decide $ p, q $ **.
In general, $ p and q $ are not too close so that $ n = pq $ fits the key length (4,096bit here) and $ p and q $ have the same number of digits (2,048bit) respectively. (At least the upper 100 bits make a difference), and randomly select a prime number. Here, randomly selecting $ p $ does not change much, and by adjusting ** $ q $ by calculating back from the range of n **, the range of $ n $ can be adjusted in the end. Random.
The calculation contents of the tool created this time are roughly as follows.
Therefore, "how to find a prime number" is the center of the calculation, and the following two are implemented.
bn_rsa_fips186_4_derive_prime ()
in bn_rsa_fips186_4.c. ..
In addition, small prime numbers are usually searched randomly. The size is 171 bits, and this number is based on the function bn_rsa_fips186_4_aux_prime_min_size ()
of OpenSSL bn_rsa_fips186_4.c. I am doing it.In RSA, key security is dominated by the computational complexity of the number field sieving method as "difficulty of factoring $ n $", and indiscriminate search for prime candidates is not worth the attacker. Therefore, I think that the security of the key will not be reduced if this method sets a limit of several hundred bits at most in the range of prime numbers. However, we do not know what kind of defects the tool has, so we recommend that you ** only use it as a "material" **.
If you make 1 billion private keys, you can make a public key including your name with high probability, "Embedding a character string in the public key" I didn't even think of it as "Rujan". Thank you. In this tool, I wrote the key data output (ASN1), primality test, etc. all by myself, but I think it was easier and better to use the OpenSSL function obediently. I also do. How about an application of RSA, including rewriting everywhere, for free research during this summer vacation?
Recommended Posts