iTranslated by AI

The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
🙃

Creating RSA Encryption Keys Using dc(1)

に公開
shell
RSA
暗号
dc
tech

In the previous article, I had some fun generating a random prime number of about 1024 bits. Now, when it comes to the application of prime numbers, cryptography—especially RSA—is famous. This time, I will generate keys using dc (for real this time).

What is RSA Cryptography?

RSA is one of the most widely used public-key cryptosystems. Public-key cryptography is a system that uses different keys for encryption and decryption. In contrast, a system that uses the same key for both encryption and decryption is called common-key (symmetric) cryptography.

RSA's security is based on the fact that it takes an enormous amount of time (= is practically impossible) to factorize the prime factors of extremely large composite numbers. It is certainly easy to factor 33 or 57, but once it gets as large as 319,999,764,000,011, the motivation fades, and once it reaches the order of 400 digits, it will take a long time even with a computer.

RSA Procedure

RSA cryptography follows the steps of key generation, encryption, and decryption.

Key Generation

Key generation is performed with the following steps:

  1. Prepare prime numbers p and q.
  2. Calculate n = p \cdot q and L = (p-1)(q-1).
  3. Prepare an integer e that is smaller than L and coprime to L.
  4. Calculate the modular multiplicative inverse d of e modulo L, such that d \equiv e^{-1} \!\!\mod L.
  5. d is the private key, and n and e are the public keys.

Encryption

To obtain ciphertext b from plaintext a, calculate b = a^e \!\!\mod n.

Decryption

To obtain decrypted text a' from ciphertext b, calculate a' = b^d \!\!\mod n.

Commonly Used Key Formats

RSA cryptography is all around us. It is so familiar that almost everyone must have created a key using ssh-keygen or openssl genrsa. First, let's observe a proper key made using these tools. Note that we will specifically handle the private key here. This is because, in most cases, the public key can be generated from the private key.

First, let's create a key. I'll just make one randomly.

$ openssl genrsa 2048 >private-key.pem
Generating RSA private key, 2048 bit long modulus (2 primes)
.......(Omitted because I was unlucky with prime numbers)........+++++
....+++++
e is 65537 (0x010001)

Let's take a look at the generated file.

$ cat private-key.pem
-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEAw8ivTldspOaSN3l1hQe+lkU092zOjehfS8c2xXLessl3keCl
yQs1EHfDMDxKTX1eJKpo6HgdFgCYu+BEoj2yTlCDLNUnUZdo+OsqKz2JBPcLOLPt
                (etc...)
0kaz492dtWdpM1gP2SiGF8GhwQxxGnUuRqjWZAHfSPH2gxURQxuQ7rfK9JwrIw+b
3e5VLq6jtGKDN0T3mmR1YBYuvHZh/5rVKfu+a5U025GquqeeBFQk
-----END RSA PRIVATE KEY-----

The generated file is some kind of mysterious text file. As you can see, this file (mostly) is encoded in base64. This format seems to be called the PEM format.

Next, the path is clear. Decode the base64-encoded part and examine its contents.

$ cat private-key.pem | sed -e '/^-----/d' | base64 -d | od -tx1
0000000 30 82 04 a3 02 01 00 02 82 01 01 00 c3 c8 af 4e
0000020 57 6c a4 e6 92 37 79 75 85 07 be 96 45 34 f7 6c
                 (etc...)
0002220 16 2e bc 76 61 ff 9a d5 29 fb be 6b 95 34 db 91
0002240 aa ba a7 9e 04 54 24
0002247

Looking at a list of hexadecimal numbers doesn't immediately make sense, but fortunately, since this was designed by humans, it can be deciphered.

Offset (HEX) Value (HEX) Content
0000 30 SEQUENCE Start
0001 82, 04 a3 Length is the following 2 bytes: 0x04a3
0004 02 INTEGER Start (version)
0005 01 Length is 0x01
0006 00 00 (Does not include otherPrimeInfos)
0007 02 INTEGER Start (Value of n)
0008 82, 01 01 Length is the following 2 bytes: 0x0101
000B 00 c3 c8 ... n = \mathrm{00c3c8}\cdots_{(16)}
010C 02 INTEGER Start (Value of e)
010D 03 Length is 0x03
010E 01 00 01 e = 010001_{(16)}
0111 02 INTEGER Start (Value of d)
0112 82, 01 00 Length is the following 2 bytes: 0x0100
0115 2a cf 24 ... d = \mathrm{2acf24}\cdots_{(16)}
0215 02 INTEGER Start (Value of p)
0216 81, 81 Length is the following 1 byte: 0x81
0218 00 ec a9 ... p = \mathrm{00eca9}\cdots_{(16)}
0299 02 INTEGER Start (Value of q)
029A 81, 81 Length is the following 1 byte: 0x81
029C 00 d3 c8 ... q = \mathrm{00d3c8}\cdots_{(16)}
031D 02 INTEGER Start (Value of d \!\!\mod (p-1))
031E 81, 80 Length is the following 1 byte: 0x80
0320 06 1e 02 ... d \!\!\mod (p-1) = \mathrm{061e02}\cdots_{(16)}
03A0 02 INTEGER Start (Value of d \!\!\mod(q-1))
03A1 81, 81 Length is the following 1 byte: 0x81
03A3 00 bc c0 ... d \!\!\mod(q-1) = \mathrm{00bcc0}\cdots_{(16)}
0424 02 INTEGER Start (Value of q^{-1} \!\!\mod{p})
0425 81, 80 Length is the following 1 byte: 0x80
0427 5b 1a 9b ... q^{-1} \!\!\mod p = \mathrm{5b1a9b}\cdots_{(16)}

This byte sequence seems to be called the DER format. Base64 encoding a DER-formatted byte sequence results in the PEM format. And this (R)IFF-like data structure is apparently called ASN.1.

Writing a Binary File

To create a key in PEM format, you need to create a key in DER format, so you must be able to write binary files.

There doesn't seem to be a single standard way to manipulate binary files in shell scripts. Specific examples include using printf(1) and using xxd(1).

We have already covered reading binary files; the process of reading /dev/urandom for the prime generation in the previous article was exactly that. I pondered over how to write binary files, but don't we have dc with us? Let's use that.

$ echo "DEADBEEF" | dc -e "16i?[100~rd0!=D]dsDxs*[Pz0<P]dsPx" | od -tx1
0000000 de ad be ef
0000004

I implemented a filter using dc to convert a hexadecimal string into a byte stream. Its behavior towards a single null byte is a bit suspicious. The logic is straightforward:

  1. Load the input as a number onto the stack.
  2. Divide the top of the stack by 0x100 to get the quotient and remainder.
  3. Keep pushing remainders onto the stack until the quotient becomes 0.
  4. Output the entire stack as a byte stream.

It consumes a lot of stack space, but it worked, so I'll go with it.

Let's try writing it for now

And so, I wrote a shell script as follows. It outputs a 2048-bit key. I didn't want the script to be too long, so I hard-coded some values in places.

keygen.sh
#!/bin/sh

# Fermat's Little Theorem
# Fermat(a, n)
Fermat() {
	if [ $# -ne 2 ]; then return -1; fi
	if [ $(dc -e "0 1sP16i$1 $2d1-r|1=Pp") -eq 0 ]; then return 1; fi
	return 0
}

# True for probable primes
# isPrime(n)
isPrime() {
	if [ $# -ne 1 ]; then return -1; fi
	for i in 2 3 5 7 11 13 17 19; do
		if ! Fermat $i $1; then return 1; fi
	done
	return 0
}

# Random number generation (Hex)
# RandGen()
RandGen() {
	od -An -N128 -tx8 /dev/urandom | \
		sed -ze 's/\(.*\)/\U\1/g; s/[[:space:]]//g'
}

# Prime number generation (Hex)
# PrimeGen()
PrimeGen() {
	p=$(RandGen)
	while ! isPrime $p; do p=$(RandGen); done
	echo $p
}

# Convert hexadecimal to byte stream
# binarize(hex)
binarize() {
	if [ $# -ne 1 ]; then return -1; fi
	dc -e "16i$1[100~rd0!=D]dsDxs*[Pz0<P]dsPx"
}

# Convert hexadecimal to byte stream with specified number of digits
# binarize2(hex, n)
binarize2() {
	if [ $# -ne 2 ]; then return -1; fi
	dc -e "16i$1[100~rd0!=D]dsDxs*[q]sQ$2sn[zln!>Q0lNx]dsNx[Pz0<P]dsPx"
}

# Convert hexadecimal to unsigned byte stream
# key_binarize(hex)
key_binarize() {
	if [ $# -ne 1 ]; then return -1; fi
	dc -e "16i$1[100~rd0!=D]dsDxs*0sqd7F<q[Pz0<P]dsPx"
}

# Assemble private key
# BuildPriKey(n, e, d, p, q, dp1, dq1, q1p)
BuildPriKey() {
	if [ $# -ne 8 ]; then return -1; fi

	tempkey=$(tempfile)
	tempseq=$(tempfile)
	tempval=$(tempfile)

	# Version
	binarize '020100' >$tempseq
	# n (Hard-coded size 2 bytes)
	binarize '0282' >>$tempseq
	key_binarize "$1" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempseq
	cat $tempval >>$tempseq
	# e (Hard-coded 3 bytes)
	binarize '0203' >>$tempseq
	key_binarize "$2" >>$tempseq
	# d (Hard-coded size 2 bytes)
	binarize '0282' >>$tempseq
	key_binarize "$3" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempseq
	cat $tempval >>$tempseq
	# p (Hard-coded size 1 byte)
	binarize '0281' >>$tempseq
	key_binarize "$4" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq
	# q (Hard-coded size 1 byte)
	binarize '0281' >>$tempseq
	key_binarize "$5" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq
	# d mod (p-1) (Hard-coded size 1 byte)
	binarize '0281' >>$tempseq
	key_binarize "$6" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq
	# d mod (q-1) (Hard-coded size 1 byte)
	binarize '0281' >>$tempseq
	key_binarize "$7" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq
	# q^-1 mod p (Hard-coded size 1 byte)
	binarize '0281' >>$tempseq
	key_binarize "$8" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq

	# Key body (Hard-coded size 2 bytes)
	binarize '3082' >$tempkey
	binarize2 $(cat $tempseq | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempkey
	cat $tempseq >>$tempkey

	# Display the private key itself
	echo '-----BEGIN RSA PRIVATE KEY-----'
	base64 -w64 $tempkey
	echo '-----END RSA PRIVATE KEY-----'

	rm -f $tempkey $tempseq $tempval
}

# Create the modular multiplicative inverse of n modulo k
# Inverse(n, k)
Inverse() {
	if [ $# -ne 2 ]; then return -1; fi
	dc -e "
		16doi				# Hexadecimal I/O
		$2 dsasL$1 sb			# L = a = k; b = n;
		1sx0sy				# x = 1; y = 0;
		1ss				# s = +1
		[q]sQ				# Exit macro
		[				# do {
			lb1=Q			#     if (b == 1) break;
			lalb~smsd		#     d = a / b; m = a % b;
			lbsa lmsb		#     b = a; m = b;
			ldlx*ly+st		#     t = d * x + y;
			lxsy ltsx		#     y = x; x = t;
			ls_1*ss			#     s = s * -1;
			lWx			# }
		]dsWx				# while (1)
		[lL+]sP				# Macro to handle negative values
		lslx*d0>Pp			# Output as positive
		" | sed -ze 's/[[:space:]\\]//g'
}

# Generate a key
# BuildKey(filename)
BuildKey() {
	if [ $# -ne 1 ]; then return -1; fi
	p=$(PrimeGen)
	echo "P"
	q=$(PrimeGen)
	echo "Q"
	n=$(dc -e "16doi $p $q *p" | sed -ze 's/[[:space:]\\]//g')
	L=$(dc -e "16doi $p 1-$q 1-*p" | sed -ze 's/[[:space:]\\]//g')
	e='10001'
	d=$(Inverse $e $L)
	dp1=$(dc -e "16doi $d $p 1-%p" | sed -ze 's/[[:space:]\\]//g')
	dq1=$(dc -e "16doi $d $q 1-%p" | sed -ze 's/[[:space:]\\]//g')
	q1p=$(Inverse $q $p)

	# Generate private key content
	umask 077
	BuildPriKey "$n" "$e" "$d" "$p" "$q" "$dp1" "$dq1" "$q1p" >$1
}

if [ $1 ]; then
	KEYNAME=$1
else
	KEYNAME=$(mktemp -u ./HOBBY-KEY.XXXXX)
fi

BuildKey $KEYNAME

Let's try running it

Depending on the mood of the random numbers and your daily behavior, it will take anywhere from a few minutes to over ten minutes to complete. Most of the processing time is spent on prime generation.

$ sh keygen.sh
P
Q
$ ls HOBBY-KEY.*
HOBBY-KEY.zG5x2

Using the generated key

Let's actually use the generated key.

Creating a public key from a private key

Use the openssl rsa command. By using this command, you can obtain a public key from a private key at any time.

$ openssl rsa -in HOBBY-KEY.zG5x2 -pubout -out HOBBY-KEY.pub

Encrypting a file using the public key

First, let's create a dummy file. In this case, we'll greet the world.

$ echo "Hello, World!" >hoge.txt

To encrypt a file, specify -encrypt with openssl rsautl.

$ openssl rsautl -encrypt -pubin -inkey HOBBY-KEY.pub -in hoge.txt -out hoge.encrypted

The resulting hoge.encrypted is the encrypted file. It is a binary file.

$ od -x hoge.encrypted
0000000 ae13 6652 09b4 1ebb d082 926d 05f7 c79a
0000020 6354 8b22 7ec3 70ef 2d16 3bad 1471 ea77
                (etc...)
0000340 eafb 74af 300c 823b 6726 021c a684 a493
0000360 01fa ac4a 39cb eaba 485d e48c c0d0 d882
0000400

Decrypting a file using the private key

The encrypted file is decrypted using the private key.

$ openssl rsautl -decrypt -inkey HOBBY-KEY.zG5x2 -in hoge.encrypted
Hello, World!

Summary

By writing a simple shell script using dc, I was able to generate a PEM format RSA private key (2048 bit) on my own. If you spend even more time on key generation, you could probably generate a 4096-bit key. It would be even better if the speed of prime generation could be improved. Although it was by no means a practical script (both last time and this time), it was a good learning opportunity.

Bonus (Example of a generated key)

I'll include an example of a private key generated in my local environment. I hope it's useful for something...

Generated Private Key
-----BEGIN RSA PRIVATE KEY-----
MIIEoQIBAAKCAQASPrWNBxFL3MCrC+pirTP5iT11tI9jk2r/aASS8iLD6cHxqyob
iPgISlHB22REzIJB8hKaNfj0YbhjIrYDTM+W/PG3RqIl6lborBHe6wZsFgiPIiP+
wATtfwVjndual71/zmfqFWdnTfCB1cDEHqsgHNZtI76KMGpqywXf1jVtxAl6MHMl
eLokU7RqPDRUyuaKzdH6P1OwW+BYMZ67Z68D5migAfmGvQC4tBW97QLoyXpfIPot
2NG40Rj5mLlY4jQkKbqfBEKsjvaOXpyzCiUuhFt11bxQTJdubfSeO1E9chcT8XMt
C9mqiWzfYXOEIHvtcl5eh9VC1M/k12Tn1ADtAgMBAAECggEADp8Cj0oiqlD2dhzO
cNWs2UUKY9GXN41kKdoKEFjLU4V5T1qEHBzf6ITmkBxpdlkN6hs8nSizoeTOB2RB
yNM9aRq7+sw4FXp+u2dpyuM9+lCN+2a4webQDCPHBdXzryf7TPj0fbs5aqgjHWlX
WdPZ/5ocnMoQYF38aijZRFA98QByBsaqW5tMwqEYRZMb8cBJZq0Ab3B6PsiWmNmI
0pKotX6um1Fyz7PVvCUGe8+8/aHbNVeM1X3Bw6xyuODY46O7f1cARwlRoMgznCnA
5EiB/zPeOmg493FFFta9vvENndnB6DBVm1b9JaAOh6coIK1ayrGIqYiAu7bxeXAZ
a68NYQKBgQDZDm2DGJCI3BzOHhoiG/g3QnDNyWekKRG1BoWdkturpIdNUPILABT6
s6XInhlkRHdOZ0LPohvda6lIJyBhTPA7jgOR5QV5LxkZl6V/6IYPX6qRWg21ad8F
SzN58vi/Jra3FymgA2kTmArQqtS7G0FLpjcNiAcy2lc7U+B6i2i6FwKBgBWEtvX3
bq7u2WBRdXku5dDSuWYpqb3h0k/3jfhxS0QaWpowD6r7S8ZNdJxHiCk94zpSel5E
Z3tLQOWoiI6eCSNZRCXZuqj/TcFVkivQR8TRR2CE9SCZZxNdi7jCgbhFGYJfCUTG
czKmYECHvJFgdhS/bmHnEczuSGfCcOp1pXObAoGAF+HxhMowJQ7rEHbZc0VWk2X5
GXt+rt5h92QnUYY2K3Wn+Ybdiv5QUKFxrVhP/OtXoUXVYRk6LavJ7Yl4k5wulq7y
j5v+dS4Mefdom2FPVuO01ddtyLdEdcWnfVSRsB6nXg/rYZLefextzDXvwEKodZVt
W0zLVfoWPQ3mljU+qbMCgYABUpLcM0T+Q3fgz6DkvdkqKIl0mgLwxLxkZda3+l6h
5OzEpUeRPri9i20rXcoknsUkhIU43gNuNIXcl6ss+NGe9pGVsfgjAu4If/Xn83k1
w5cbe5CFXGhVbF52EJ5gcP7MYIL1Uy0pY8hurukMFl2rkMh8A/O4IL0ag3zlLC3r
GQKBgQCxyrNfhYpl0m8lECx1el1h3SFE0fVkcoo1UlSLe74iQ1d9SofFMLVKowFQ
g0Vs4GXjB9atFtSYuX02DfkdAtndIDK6NZeXbP8+YNoNmcfBzN6GH6uEK5Lg6VcP
8ZtAb4ZCpXZZzQu82SvWxESTzEGAWZ/nJLhx+zbPnZPi1GHbQw==
-----END RSA PRIVATE KEY-----

Update (03-27)

In random number generation, since the generated numbers include even numbers, I thought generating odd random numbers could halve the number of generation cycles. So, I changed it as follows. I feel like it got a bit faster, but I'm not sure of the actual results:

Changes
@@ -25,11 +25,17 @@
 		sed -ze 's/\\(.*\\)/\\U\\1/g; s/[[:space:]]//g'
 }
 
+# Generate odd random numbers (Hex)
+# RandOddGen()
+RandOddGen() {
+	dc -e "16doi$(RandGen) 2/d1++p" | sed -ze 's/[[:space:]\\\\]//g'
+}
+
 # Prime number generation (Hex)
 # PrimeGen()
 PrimeGen() {
- 	p=$(RandGen)
- 	while ! isPrime $p; do p=$(RandGen); done
+ 	p=$(RandOddGen)
+ 	while ! isPrime $p; do p=$(RandOddGen); done
 	echo $p
 }

References

  1. @kunichiko, OpenSSL command for public key cryptography and digital signatures (Japanese). Updated 2018-10-10, Accessed 2021-03-25.
  2. Issei Numata, Calculating modular multiplicative inverse Part 2 (Japanese). Published 2013-11-21, Accessed 2021-03-23.
  3. bearmini, RSA Private/Public Key File Formats (Japanese). Published 2014-02-05, Accessed 2021-03-23.

Discussion