With RSA, you can create a public key that includes your favorite character string

Introduction

background

• Note: This was inspired by If you make 1 billion private keys, you can make a public key including your name with high probability. It is a story article

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 **.

Created tool

specification

• A single Ruby script.
• Located at https://github.com/angel-p57/qiita-sample/blob/master/rsa/rsa-genmykey.rb
• Output the RSA SSH private key (not new in OpenSSH format) by specifying a string of your choice in the command line arguments.
• Please save to a file by redirect etc.
• The key length is fixed at 4,096.
• The character types that can be specified in the character string are 64 types of alphanumeric characters and +/. (That is, base64 character type)
• In principle, the length of the character string that can be embedded can be quite long, but the tool limits the length to 64 characters.
• Since it has not been tuned in particular, please consider that it will take several tens of seconds to minutes to execute. (There is a lot of blurring even in the same environment)

Example of use

Below is an example of when I actually made it and tried it.

1. Private key generation It is saved as ruby rsa-genmykey.rb embedded character string> save destination file name.
2. Public key extraction Since the tool only creates private key data, the public key is extracted with ssh-keygen -y -f private key file> save destination file name.
3. Trial We have actually registered the public key in the connection destination with ssh-copy-id and confirmed that it can be used for public key authentication.

Karakuri

Contents of public key

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.

• The most significant digit is randomly determined within a certain range.

Adjusting key parameters

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.

Calculation contents

The calculation contents of the tool created this time are roughly as follows.

1. Determine the range of $ n $ from the string to be embedded
2. Determine the range of the prime number $ p $ (range that is greater than or equal to $ \ sqrt {n} $)
3. Determine a random prime number $ p $ within the range
4. Determine the range of the prime number $ q $ from the value of $ p $ and the range of $ n $
5. Determine a random prime number $ q $ within the range
6. Generate key data based on the values of $ p and q $

Therefore, "how to find a prime number" is the center of the calculation, and the following two are implemented.

• Primality test The Miller-Rabin judgment method has been implemented as it is. Since the number of trials is 40, the probability of false judgment is $ 1/2 ^ {80} $, so I don't think it will be a problem in practice. See Appendix C, C.3.1 at FIPS186-4 for more information.
• Search for prime number candidates We have implemented a method to search for candidates for prime numbers of the desired size from two smaller prime numbers. See Appendix C, C.9 of FIPS186-4 for more information. I haven't scrutinized it in detail, but I think it's more efficient than searching for candidates in the dark clouds. OpenSSL also seems to adopt this method as the function 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.

Key security

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" **.

At the end

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?