秘密のバックドアのあるPGP鍵ソースコード

暗号を使おう！

秘密のバックドアのあるPGP鍵ソースコード

Date: Sat, 1 Jun 1996 14:16:12 +0200
To: cypherpunks@toad.com
From: Gary Howland <gary@systemics.com>
Subject: Re: RSAにバックドア（Backdoor）発見
Sender: owner-cypherpunks@toad.com
Precedence: bulk

やあ。

これは、生成されたときに秘密のバックドアのあるPGP鍵の例です。生成された鍵を見るだけでは、これにバックドアがあることはわかりません。

鍵生成コードには、木づち(Mallets)公開鍵が含まれています。鍵を生成するとき、Nの上位バイトはNの暗号化された因数に設定されます。暗号化は木づち公開鍵を使ってなされ、木づちだけがNからの因数を回復させることができます。

この例は、鍵生成ソースコード（それは乱数生成装置の品質を検証するためにも結局必要ですが）だけではなく、このソースをコンパイル・リンクすることができる必要性を示しています。というのも、この能力がなければ、このようなバックドアをシステムに組み込むのはあまりにも簡単になってしまうからです（そう、このコードは逆設計されうるものですが、自己修正コードなどを持つことによって非常にむずかしいものにできるのです）。

しかし、こんなペテンが続かないようユーザーに保証する方法が一つあるようです。これは、PGPアスキー鍵に現われるようなフレーズをユーザーが特定できるようにする「虚飾(vanity)鍵」で生成されることで可能です。もしこうすれば、この機能についての詳細を保存できるような余地は、Nにはほとんど残らないでしょう。

これが、このバックドアの効いている例です。

これが木づち秘密鍵（パスフレーズは "xyzzy"）

Type bits/keyID    Date        User ID
sec   496/5D925633 1996/06/01  Bill Klinton <bill@whitehouse.gov>
-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.2

QD5AjGwJnsAAAEB8M6FnxIdQZrORfKlb6/l74S6YUT0GQHvzrioiXJoRd2gnAAs
e99C/XPKZShiylm+nu5UD8zDBBtcoiBdklYzAAURAQxi1EDMl1u+Aew7e7bKTY6c
l/RAUacgZ9zbL1tl96kxQucLrt8l6Sz11EOmnV9eDZdf1LYG9jg5WbLvNGqpmzyY
PlNKBJn/7gD4hu3YUt9caDyY5/X2ASMaL40gb1y1YZxjbTbB4Xjd8wD4+Iv9qhEQ
fLjeYi+iUhnNkMtPyeg/+TR6rdP/c42UXAD2mqW0VuM8wiib0nbwfXwC0SlJveLG
UwNOgRIujTwS7k35tCJCaWxsIEtsaW50b24gPGJpbGxAd2hpdGVob3VzZS5nb3Y+
=oOrI
-----END PGP SECRET KEY BLOCK-----

鍵は以下のもので構成されています。

n:	ce859f121d419ace45f2a56fafe5ef84ba6144f41901efceb8a889726845dd
	a09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633
e:	11
d:	0c25fa4c5c12eafd132c6415a0ef68713823d6e12ea5c2cfecbe9eac607c94
	75d1b60c2a3aef89438692326d70d88080317b0cd04432d5a0230de572e819
p:	d2640ede17e8c05545aa9ecfd5154f934021e4ef8ef22a248abe0ab3f1aaed
q:	fb4ada7f960c9a8ab23010ff4936a9a2db834346694979c72f90296cff419f

これはJoeのPGP鍵（パスフレーズは "xyzzy"）

Type bits/keyID    Date        User ID
sec  1024/D0351D23 1996/06/01  Joe Sixpack <joe@aol.com>
-----BEGIN PGP SECRET KEY BLOCK-----
Version: 2.6.2

lQHgAjGwKUIAAAEEAIBG2pH3rabYMSWhVjcnG8v9HVU4vwtBuBysnvuJI4PvjV3o
+YnuFD+x3aF8O52jgpBTllAxhndDSPUXQaj+sXEGDkV0Nq8RCZ02usaj24ogn0+S
KW9ej8GgWL8EmlP1H1Qrv39/qz1VSqvxczCLYoRetHETR0JirwcMj9fQNR0jAAUR
AYwvF+QHqifbA/4oAli05pLm0QlkbOqimdm4QS3OC1r9kdqvO88GF5nj9EgLm1a+
svRThXiO586Udi1UkSXvM60o4nz6tGASavgc7X8JaL/B2yOcMH9gF6CN6zabiyAb
anrJe06IuKH3980GoQ2Sp1sssFHqxgper1ga3STmUVj/dQBjaFUI1qwDkwIAnRPO
F7qIopIcEhnxW1OXcv0/9Afhugy3ERbGZwTaaw2fAiiyD41FpkbOUbao8D5Vkndr
y6h2LEC7P5iwfdAF3AIAPz/2nRuZAnyNrA4ESvryyHMejwsz9BAkok+MT2z2E85W
h8laL76yok5DZz56bRqH2gyQkPR5Rx3hnLx+fqL45gIAzy3CkdR77yw8bXUH8/Av
azYh0m4KzEsw8P1a10YkVxP8xiTbqYbN0lmzOrdWlEW6dZjkx5q67vt1op7hDtqW
LJwYtBlKb2UgU2l4cGFjayA8am9lQGFvbC5jb20+
=evl9
-----END PGP SECRET KEY BLOCK-----

鍵は以下のもので構成されています。

n:	8046da91f7ada6d83125a15637271bcbfd1d5538bf0b41b81cac9efb89
	2383ef8d5de8f989ee143fb1dda17c3b9da382905396503186774348f5
	1741a8feb171060e457436af11099d36bac6a3db8a209f4f92296f5e8f
	c1a058bf049a53f51f542bbf7f7fab3d554aabf173308b62845eb47113
	474262af070c8fd7d0351d23
e:	11
d:	2d462f06576a771f2067a25aaa0dcd934a46968c7fa99eb97388381c8a
	c13d9fd78a8e7630ae617fe46c571cc9bf2aa68d4aad85b7206653fba1
	cbf90e78026398a33f3a99dd4ced780f9bd854b2560f5cd9c6113ab837
	7443d9e946a3c2c74989f26f775635cd6ebd8a665e0885e28c60d714b3
	c9981c0ff09fa561a7d7d8f1
p:	804e00dc8ea1c0a55c2f5a5b14fdb05f84ecb1c5d1463562925637624e
	6f1d945adbc4ed2cb4dd266f8f9c59f6c07d7b3d3ee20328bfdf12f54f
	654256a63e01
q:	fff1bc1c496fa118c2307c31498f3b403df9d9dd77b91295a3191d5a26
	924d8ff276696adeb344ca6cbeddb976fa387b64697f12b8a8dec43d4e
	2b561e005633

nの1-63バイトを見るなら、

46da91f7ada6d83125a15637271bcbfd1d5538bf0b41b81cac9efb892383ef 8d5de8f989ee143fb1dda17c3b9da382905396503186774348f51741a8feb1

そして、木づちのプライベート 'd'を使って復号化すれば、こうなります。

4e00dc8ea1c0a55c2f5a5b14fdb05f84ecb1c5d1463562925637624e6f1d94 5adbc4ed2cb4dd266f8f9c59f6c07d7b3d3ee20328bfdf12f54f654256a63e

あなたは、Joeの Pのうち、最初の 0x80と最後の0x01がないものを見ることができます。

これは、Joeの鍵を生成したコード（Perl）です。
このコードは、木づち公開鍵だけを含んでいます。

my $bits = 512;	# Bits in p and q, not in n

#
#	木づち公開鍵の設定
#
my $me = new MPI 17;
my $mn = restore MPI pack("H*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efc
eb8a889726845dda09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");

#
# 注　最初のバイトは0x80
# 第２バイトの最初のビットはゼロ。
# これはPが木づちのnより小さくするため。
#
my $p;
do {
	$p = randomSpecial($bits, "100000000", "00000001");
} while (!isPrime($p));

#
#	木づちのためのPを暗号化
#
my $ss = $p->save();
substr($ss, 0, 1) = '';	# Remove high and low bytes
substr($ss, -1, 1) = ''; # since we know what they are
my $tmp = restore MPI $ss;
my $s = new MPI;
MPI::mod_exp($s, $tmp, $me, $mn);
$s = restore MPI pack("C", 128) . $s->save() . pack("C", 1);

my $tmp = new MPI;
my $q = new MPI;

MPI::lshift($tmp, $s, $bits);
MPI::add($tmp, $tmp, new MPI 256);	# Qが大きくなりすぎないように
MPI::div($q, new MPI, $tmp, $p);

do {
	$q->inc();
} while (!isPrime($q));


my $e = new MPI 17;
my $sk = RSAKeyGen::deriveKeys($p, $q, $e);

#
#	我々の鍵をセーブ
#
my $passphrase = "xyzzy";
my $skc = new SecretKeyCertificate($sk, $passphrase);

my $fos = new FileOutputStream("secring.pgp");
my $dos = new DataOutputStream($fos);

$skc->saveToDataStream($dos);

my $id = new UserIdPacket 'Joe Sixpack <joe@aol.com>';
$id->saveToDataStream($dos);

これは、Joeの公開鍵からPを復元するためのコード（木づちの秘密鍵が必要）


#
# 木づち秘密鍵
#
my $mn = restore MPI pack("H*", "ce859f121d419ace45f2a56fafe5ef84ba6144f41901efc
eb8a889726845dda09c002c7bdf42fd73ca652862ca59be9eee540fccc3041b5ca2205d925633");
my $md = restore MPI pack("H*", "0c25fa4c5c12eafd132c6415a0ef68713823d6e12ea5c2c
fecbe9eac607c9475d1b60c2a3aef89438692326d70d88080317b0cd04432d5a0230de572e819");

my $rp = new MPI;
my $pe = restore MPI substr($sk->n()->save(), 1, 62);
MPI::mod_exp($rp, $pe, $md, $mn);	# Decrypt

Gary
--
pub 1024/C001D00D 1996/01/22 Gary Howland <gary@systemics.com>
Key fingerprint = 0C FB 60 61 4D 3B 24 7D 1C 89 1D BE 1F EE 09 06

HOME > Theory > Crypt

2000年盗聴法対抗
ダウンロード／PGP6.5.1i／PGP disk／
日本語化／PGP鍵作成／
PGPdiskマウント／秘密鍵を隠す／
落とし穴／完全抹消法

PGP ユーザーズ・マニュアル　第１巻
 The comp.security.pgp FAQ 日本語版
 パスフレーズFAQ 日本語版
バックドア　NSA／Phrack Magazine／ソースコード
 暗号関係リンク集