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

Introduction

background

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! image.png

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;

Created tool

specification

Example of use

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

  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.

image.png

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.

Adjusting key parameters

Now, in the case of RSA, there are some key parameters (both integers).

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.

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?

Recommended Posts

With RSA, you can create a public key that includes your favorite character string
Create a page control that can be used with RecyclerView
When is it said that you can use try with a Swift error?
A ruby ​​script that creates an rsa private key that can be used with OpenSSL from any two prime numbers
Create a private key / public key in CentOS8.2 and connect to SSH with VS Code
(For myself) Build an IDE that you can touch from a browser with docker (trial)