Zenn
🙃

dc(1) を使って RSA 暗号の鍵を作ってみる

2021/03/25に公開
shell
rsa
暗号
dc
tech

前回の記事では 1024 bit 程度の適当な素数を生成して遊びました． さて，素数の応用といえば暗号，とりわけ RSA 暗号は有名です． 今回は dc を (今度こそ) 利用して鍵を生成します．

RSA 暗号とは

RSA 暗号は広く利用されている公開鍵暗号のひとつです． 公開鍵暗号とは，暗号化と復号に異なる鍵を用いる暗号です． これに対して，暗号化と復号に同一の鍵を用いる暗号を共通鍵暗号といいます．

RSA 暗号は，非常に大きい合成数の素因数分解に膨大な時間がかかる (= 事実上不可能である) ことを安全の根拠としています． 確かに，33 や 57 を素因数分解することは簡単ですが，319999764000011 まで大きくなるとやる気もおきませんし，400 桁オーダくらいになってくると計算機を使っても時間がかかるでしょう．

RSA 暗号の手順

RSA 暗号は，鍵の生成，暗号化，復号の手順で行います．

鍵の生成

鍵の生成は次の手順で行います:

  1. 素数 p と q を用意します．
  2. n = p \cdot q，L = (p-1)(q-1) を計算します．
  3. L と互いに素で，L より小さい整数 e を用意します．
  4. L を法とした e の逆数 d \equiv e^{-1} \!\!\mod L を計算します．
  5. d が秘密鍵，n と e が公開鍵です．

暗号化

平文 a から 暗号文 b を得るには，b = a^e \!\!\mod n を計算します．

復号

暗号文 b から復号文 a' を得るには，a' = b^d \!\!\mod n を計算します．

よく使われる鍵のフォーマット

RSA 暗号は身近なところにあります． とても身近なので，誰しも ssh-keygen や openssl genrsa を使って鍵を作ったことがあるはずです． まずはこれを使って作られた正規の鍵を観察してみましょう． なお，ここでは秘密鍵を特に扱います． 大抵の場合，公開鍵は秘密鍵から生成可能であるからです．

まずは鍵を作ります． 適当に作ります．

$ openssl genrsa 2048 >private-key.pem
Generating RSA private key, 2048 bit long modulus (2 primes)
.......(素数に嫌われていたので省略)........+++++
....+++++
e is 65537 (0x010001)

生成されたファイルを眺めてみましょう．

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

生成されたファイルは何やら怪しげなテキストファイルです． 見てわかるように，このファイル (の大部分) は base64 でエンコードされています． この形式を PEM 形式というようです．

次にやることは決まっています． Base64 でエンコードされた部分をデコードし，その内容を眺めます．

$ 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
                 (ほげほげ〜)
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

16 進数の羅列を見ても何が何だか分かったもんじゃありませんが，幸いにもこれは人間が設計したものなので読み解くことができます．

オフセット (HEX) 値 (HEX) 内容
0000 30 SEQUENCE 開始
0001 82, 04 a3 長さは続く 2 バイト: 0x04a3
0004 02 INTEGER 開始 (version)
0005 01 長さは 0x01
0006 00 00 (otherPrimeInfos を含まない)
0007 02 INTEGER 開始 (n の値)
0008 82, 01 01 長さは続く 2 バイト: 0x0101
000B 00 c3 c8 ... n = \mathrm{00c3c8}\cdots_{(16)}
010C 02 INTEGER 開始 (e の値)
010D 03 長さは 0x03
010E 01 00 01 e = 010001_{(16)}
0111 02 INTEGER 開始 (d の値)
0112 82, 01 00 長さは続く 2 バイト: 0x0100
0115 2a cf 24 ... d = \mathrm{2acf24}\cdots_{(16)}
0215 02 INTEGER 開始 (p の値)
0216 81, 81 長さは続く 1 バイト: 0x81
0218 00 ec a9 ... p = \mathrm{00eca9}\cdots_{(16)}
0299 02 INTEGER 開始 (q の値)
029A 81, 81 長さは続く 1 バイト: 0x81
029C 00 d3 c8 ... q = \mathrm{00d3c8}\cdots_{(16)}
031D 02 INTEGER 開始 (d \!\!\mod (p-1) の値)
031E 81, 80 長さは続く 1 バイト: 0x80
0320 06 1e 02 ... d \!\!\mod (p-1) = \mathrm{061e02}\cdots_{(16)}
03A0 02 INTEGER 開始 (d \!\!\mod(q-1) の値)
03A1 81, 81 長さは続く 1 バイト: 0x81
03A3 00 bc c0 ... d \!\!\mod(q-1) = \mathrm{00bcc0}\cdots_{(16)}
0424 02 INTEGER 開始 (q^{-1} \!\!\mod{p} の値)
0425 81, 80 長さは続く 1 バイト: 0x80
0427 5b 1a 9b ... q^{-1} \!\!\mod p = \mathrm{5b1a9b}\cdots_{(16)}

このバイト列を DER 形式というようです． DER 形式のバイト列を base64 エンコードすると PEM 形式になります． そして，この (R)IFF のようなデータ構造を ASN.1 というようです．

バイナリファイルを書き出す

PEM 形式の鍵を作るには DER 形式の鍵を作る必要があるので，バイナリファイルを書けるようになる必要があります．

シェルスクリプトでバイナリファイルを操作する際のこれといった定石は存在しないようです． 具体的な例では，printf(1) を使った方法や xxd(1) を使った方法がありました．

バイナリファイルの読み込みはすでに完了しています． 前回の素数生成の /dev/urandom を読み込む処理はそれに違いありません． バイナリファイルを書き出す方法をウンウン考えてみましたが，私達は dc がついているではありませんか． それを使いましょう．

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

dc を使って 16 進数文字列をバイトストリームに変換するフィルタを実装しました． ヌルバイト単体に対する動作は怪しげです． 動作は愚直そのものです:

  1. 入力を数値としてスタックに積む
  2. スタック先頭を 0x100 で割り，商と余りを得る
  3. 商が 0 になるまで余りをスタックに積み続ける
  4. スタックを全部バイトストリームとして出力する

スタックの浪費が激しいですが，動いたので良しとします．

とりあえず書いてみる

そして次のようにシェルスクリプトを書きます． 2048 bit な鍵を出力します． あまり長いスクリプトにしたくなかったのでところどころ値を決め打ちしている箇所があります．

keygen.sh
#!/bin/sh

# フェルマの小定理
# 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
}

# 確率的素数で真
# 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
}

# 乱数発生 (16 進)
# RandGen()
RandGen() {
	od -An -N128 -tx8 /dev/urandom | \
		sed -ze 's/\(.*\)/\U\1/g; s/[[:space:]]//g'
}

# 素数発生 (16 進)
# PrimeGen()
PrimeGen() {
	p=$(RandGen)
	while ! isPrime $p; do p=$(RandGen); done
	echo $p
}

# 16 進数をバイトストリームに変換する
# binarize(hex)
binarize() {
	if [ $# -ne 1 ]; then return -1; fi
	dc -e "16i$1[100~rd0!=D]dsDxs*[Pz0<P]dsPx"
}

# 16 進数を桁数指定付きでバイトストリームに変換する
# 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"
}

# 16 進数を符号付きでないバイトストリームに変換する
# 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"
}

# 秘密鍵を組み立てる
# 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 (サイズ 2 バイト決め打ち)
	binarize '0282' >>$tempseq
	key_binarize "$1" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempseq
	cat $tempval >>$tempseq
	# e (3 バイト決め打ち)
	binarize '0203' >>$tempseq
	key_binarize "$2" >>$tempseq
	# d (サイズ 2 バイト決め打ち)
	binarize '0282' >>$tempseq
	key_binarize "$3" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempseq
	cat $tempval >>$tempseq
	# p (サイズ 1 バイト決め打ち)
	binarize '0281' >>$tempseq
	key_binarize "$4" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq
	# q (サイズ 1 バイト決め打ち)
	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) (サイズ 1 バイト決め打ち)
	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) (サイズ 1 バイト決め打ち)
	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 (サイズ 1 バイト決め打ち)
	binarize '0281' >>$tempseq
	key_binarize "$8" >$tempval
	binarize2 $(cat $tempval | wc -c | awk -e '{ printf "%X", $1 }') 1 \
		>>$tempseq
	cat $tempval >>$tempseq

	# 鍵本体 (サイズ 2 バイト決め打ち)
	binarize '3082' >$tempkey
	binarize2 $(cat $tempseq | wc -c | awk -e '{ printf "%X", $1 }') 2 \
		>>$tempkey
	cat $tempseq >>$tempkey

	# 秘密鍵自身の表示
	echo '-----BEGIN RSA PRIVATE KEY-----'
	base64 -w64 $tempkey
	echo '-----END RSA PRIVATE KEY-----'

	rm -f $tempkey $tempseq $tempval
}

# k を法とする n の逆数を作る
# Inverse(n, k)
Inverse() {
	if [ $# -ne 2 ]; then return -1; fi
	dc -e "
		16doi				# 入出力は 16 進数
		$2 dsasL$1 sb			# L = a = k; b = n;
		1sx0sy				# x = 1; y = 0;
		1ss				# s = +1
		[q]sQ				# 脱出用マクロ
		[				# 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				# 負値を正側に持ってくるマクロ
		lslx*d0>Pp			# プラスにして出力
		" | sed -ze 's/[[:space:]\\]//g'
}

# 鍵を作る
# 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)

	# 秘密鍵の内容を生成
	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

実行してみる

乱数の機嫌と日頃の行いによりますが，数分から十数分くらいで完了します． 処理時間の殆どは素数生成です．

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

生成された鍵を使ってみる

生成された鍵を実際に使ってみましょう．

秘密鍵から公開鍵を作る

openssl rsa コマンドを利用します． このコマンドを利用すれば，いつでも秘密鍵から公開鍵を得られます．

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

公開鍵を使ってファイルを暗号化する

まずは適当なファイルを作りましょう． 今回は世界に挨拶することにします．

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

ファイルを暗号化するには openssl rsautl で -encrypt を指定します．

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

生成される hoge.encrypted が暗号化されたファイルです． バイナリファイルになっています．

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

秘密鍵を使ってファイルを復号する

暗号化されたファイルは秘密鍵を使って復号します．

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

まとめ

dc を利用した簡単なシェルスクリプトを記述することで PEM 形式の RSA 秘密鍵 (2048 bit) を自力で生成することができました． 鍵生成にさらなる時間を費やせば 4096 bit の鍵も生成できるでしょう． 素数生成の速度を向上させることができれば更に良いです． (前回，前々回ともに) 決して実用的なスクリプトではありませんでしたが，良い勉強の機会となりました．

おまけ (生成される鍵の例)

手元の環境で生成された秘密鍵の例を添えておきます． 何かの役に立つでしょうか……

生成された秘密鍵
-----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-----

追記 (03-27)

乱数生成において，生成される数には偶数も含まれるので，奇数の乱数を生成すれば乱数生成の回数を半減できるのでは？ と思ったので次のように変更してみました． 何だか早くなった気がしないでもないですが，実際のところはどうなのかわかりません:

変更箇所
@@ -25,11 +25,17 @@
 		sed -ze 's/\(.*\)/\U\1/g; s/[[:space:]]//g'
 }
 
+# 奇数乱数生成 (16 進)
+# RandOddGen()
+RandOddGen() {
+	dc -e "16doi$(RandGen) 2/d1++p" | sed -ze 's/[[:space:]\\]//g'
+}
+
 # 素数発生 (16 進)
 # PrimeGen()
 PrimeGen() {
-	p=$(RandGen)
-	while ! isPrime $p; do p=$(RandGen); done
+	p=$(RandOddGen)
+	while ! isPrime $p; do p=$(RandOddGen); done
 	echo $p
 }

参考文献

  1. @kunichiko, OpenSSLコマンドによる公開鍵暗号、電子署名の方法. 2018-10-10 更新, 2021-03-25 閲覧.
  2. Issei Numata, 法Nでの逆数を求めるその２. 2013-11-21 公開, 2021-03-23 閲覧.
  3. bearmini, RSA 秘密鍵/公開鍵ファイルのフォーマット. 2014-02-05 公開, 2021-03-23 閲覧.

Discussion