SSHの鍵を作ってみた

投稿記事 by **みけCAT** » 11年前

みなさん、SSHは便利ですよね！…え？使ったことない？それは人生の何%かはあえて言及しませんが、正の割合損していますよ！

ところで、SSH接続をするときに必ず使うような気がする「鍵」。
鍵作成ソフトでボタンを押してしばらく待ったり、指を動かしまくってしばらく待ったりすると生成されますが、
どのようにして生成されているのでしょうか？

というわけで、今回はその鍵を作ってみました。
まずはTeraTermで鍵を作り、その構造を見てみます。今回はRSAの鍵を対象とします。
RSAの鍵データには、大きく分けて比較的短い「公開鍵」と、比較的長い「秘密鍵」の2種類があります。
どちらもbase64で符号化されているので、まずはデコードしてバイナリエディタで見てみましょう。

公開鍵のフォーマットはRFC4253のSection 6.6に書かれており、RSAなら識別子、e、nを書けばよさそうです。
ここで使用されるデータ型の説明はRFC4251のSection 5にあります。
これを素直に解釈すれば、問題はなさそうです。

: SSH公開鍵のデータの構造

この表示に使用しているTSXBIN用マクロ

► スポイラーを表示

というわけで、問題は軽くググっただけではそれっぽいRFCが見つからなかった秘密鍵です。
とりあえずbase64をデコードしてバイナリエディタで開くと、公開鍵に書かれていたnのデータがあり、その下にeらしきデータも見えます。
さらに詳しく見ていくと、

CODE:

0x30 (形式情報？例えばBMPファイルなら"BM"みたいなやつ？)
これ以降のデータサイズ
0x02 0x01 0x00 (よくわからない)
0x02 nのデータ
0x02 eのデータ
(0x02 何かの整数のデータ)×6個

のような形式になっていました。
「何かの整数のデータ」は、nやeのデータと同じような形式だったので、整数と予想できました。
各整数のデータの先頭には、以下のような形式のサイズ情報があり、「これ以降のデータサイズ」も同じ形式のようでした。

サイズが0x80未満の場合は、そのまま1バイトで記録
サイズが0x80以上の場合は、まず(記録に必要なバイト数|0x80)を記録し、
次にサイズをそのバイト数のビッグエンディアンで記録

そこで、まずはbase64デコードした秘密鍵のデータをテキストに書き出すプログラムを作りました。
(注:解析したデータを後で反映させたため、データの説明が未知ではなくきちんと書かれている)

► スポイラーを表示

CODE:

#include 

int readSize(FILE* fp) {
	int input;
	int ret=0;
	input=fgetc(fp);
	if(input\n",stderr);
		fputs("\ninput file : decoded (NOT base64 encoded) id_rsa data file\n",stderr);
		return 1;
	}
	fp=fopen(argv[1],"rb");
	if(fp==NULL) {
		fputs("File open error.\n",stderr);
		return 1;
	}
	input=fgetc(fp);
	printf("maybe_type\t%02X\n",input);
	printf("data_size\t%08X\n",readSize(fp));
	for(i=0;i
#include 
#include 
#include 

static const char base64chars[]=
	"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
	"abcdefghijklmnopqrstuvwxyz"
	"0123456789+/";

typedef struct {
	FILE* fp;
	int bufferStatus;
	int linePosition;
	int lineBreak;
	unsigned char buffer;
} base64encode_t;

void base64start(base64encode_t* b64,FILE* fp,int lineBreak) {
	b64->fp=fp;
	b64->bufferStatus=0;
	b64->linePosition=0;
	b64->lineBreak=lineBreak;
}

void base64putchar(base64encode_t* b64,int c) {
	fputc(c,b64->fp);
	b64->linePosition++;
	if(b64->lineBreak>0 && b64->linePosition>=b64->lineBreak) {
		b64->linePosition=0;
		fputc('\n',b64->fp);
	}
}

void base64write(base64encode_t* b64,const void* data,int size) {
	int i;
	const unsigned char* p=(const unsigned char*)data;
	for(i=0;ibufferStatus) {
			case 0:
				b64->buffer=now;
				base64putchar(b64,base64chars[(now>>2)&0x3f]);
				b64->bufferStatus=1;
				break;
			case 1:
				base64putchar(b64,base64chars[((b64->buffer>4))&0x3f]);
				b64->buffer=now;
				b64->bufferStatus=2;
				break;
			case 2:
				base64putchar(b64,base64chars[((b64->buffer>6))&0x3f]);
				base64putchar(b64,base64chars[now&0x3f]);
				b64->bufferStatus=0;
				break;
		}
	}
}

void base64end(base64encode_t* b64) {
	switch(b64->bufferStatus) {
		/* case 0: do nothing */
		case 1:
			base64putchar(b64,base64chars[(b64->bufferfp);
			break;
		case 2:
			base64putchar(b64,base64chars[(b64->bufferfp);
			break;
	}
	b64->bufferStatus=0;
	b64->linePosition=0;
}

void writeSizeDataToBase64(base64encode_t* b64,size_t size) {
	unsigned char sizeBuffer[4];
	unsigned char count;
	int i;
	if(size0;size>>=8)sizeBuffer[count++]=size&0xff;
		count|=0x80;
		base64write(b64,(void*)&count,1);
		for(i=(count&0x7f)-1;i>=0;i--)base64write(b64,(void*)&sizeBuffer[i],1);
	}
}

void writeIntegerToBase64(base64encode_t* b64,const void* dat,size_t size,int mode) {
	unsigned char sizeBuffer[4];
	size_t writeSize;
	int i;
	if(((const unsigned char*)dat)[0]&0x80) {
		writeSize=size+1;
	} else {
		writeSize=size;
	}
	if(mode==0) {
		for(i=0;i>((3-i)*8))&0xff;
		base64write(b64,(void*)sizeBuffer,4);
	} else {
		sizeBuffer[0]=0x02;
		base64write(b64,(void*)sizeBuffer,1);
		writeSizeDataToBase64(b64,writeSize);
	}
	if(((const unsigned char*)dat)[0]&0x80) {
		sizeBuffer[0]=0;
		base64write(b64,(void*)sizeBuffer,1);
	}
	base64write(b64,dat,size);
}

int calcuateSizeOfSizeData(size_t size) {
	int ret;
	if(size0;size>>=8)ret++;
	return ret;
}

int main(int argc,char* argv[]) {
	static const char identifier[]="\x00\x00\x00\x07ssh-rsa";
	int bits=1024;
	mpz_t n,e,d,p,q,x1,x2,x3,tmp;
	gmp_randstate_t rs;
	FILE* fp;
	base64encode_t b64;
	void* n_dat=NULL;
	void* e_dat=NULL;
	void* dats[6]={};
	size_t n_size,e_size,sizes[6];
	size_t dataSize;
	int i;
	/* パラメータチェック */
	if(argc!=4) {
		fputs("Usage: generatersakey   \n",stderr);
		return 1;
	}
	/* ビット数の入力 */
	if(sscanf(argv[1],"%d",&bits)!=1 || bits=2^bits (overflow) */
	do {
		mpz_urandomb(q,rs,bits-1);
		mpz_setbit(q,bits-1);
		mpz_nextprime(q,q);
	} while(mpz_tstbit(q,bits) || mpz_cmp(p,q)==0);
	/* パラメータの計算 */
	mpz_mul(n,p,q);
	mpz_sub_ui(tmp,p,1);
	mpz_sub_ui(x1,q,1);
	mpz_mul(tmp,tmp,x1);
	if(mpz_gcd_ui(NULL,tmp,65537)==1) {
		mpz_set_ui(e,65537);
	} else if(mpz_gcd_ui(NULL,tmp,17)==1) {
		mpz_set_ui(e,17);
	} else if(mpz_gcd_ui(NULL,tmp,35)==1) {
		mpz_set_ui(e,35);
	} else if(mpz_gcd_ui(NULL,tmp,3)==1) {
		mpz_set_ui(e,3);
	} else {
		fputs("Bad luck! Key generation failed. Please try again.\n",stderr);
	}
	mpz_invert(d,e,tmp);
	mpz_sub_ui(tmp,p,1);
	mpz_mod(x1,d,tmp);
	mpz_sub_ui(tmp,q,1);
	mpz_mod(x2,d,tmp);
	mpz_invert(x3,q,p);
	/* 計算したパラメータの書き出し */
	n_dat=mpz_export(NULL,&n_size,1,1,1,0,n);
	e_dat=mpz_export(NULL,&e_size,1,1,1,0,e);
	dats[0]=mpz_export(NULL,&sizes[0],1,1,1,0,d);
	dats[1]=mpz_export(NULL,&sizes[1],1,1,1,0,p);
	dats[2]=mpz_export(NULL,&sizes[2],1,1,1,0,q);
	dats[3]=mpz_export(NULL,&sizes[3],1,1,1,0,x1);
	dats[4]=mpz_export(NULL,&sizes[4],1,1,1,0,x2);
	dats[5]=mpz_export(NULL,&sizes[5],1,1,1,0,x3);
	/* 公開鍵の書き出し */
	if((fp=fopen(argv[2],"wb"))!=NULL) {
		fputs("ssh-rsa ",fp);
		base64start(&b64,fp,0);
		base64write(&b64,(void*)identifier,11);
		writeIntegerToBase64(&b64,e_dat,e_size,0);
		writeIntegerToBase64(&b64,n_dat,n_size,0);
		base64end(&b64);
		fputs(" key\n",fp);
		fclose(fp);
	} else {
		fputs("Public key file open error!\n",stderr);
	}
	/* 秘密鍵の書き出し */
	if((fp=fopen(argv[3],"wb"))!=NULL) {
		fputs("-----BEGIN RSA PRIVATE KEY-----\n",fp);
		base64start(&b64,fp,64);
		base64write(&b64,"\x30",1);
		dataSize=3;
		dataSize+=1+calcuateSizeOfSizeData(n_size)+n_size;
		if(((unsigned char*)n)[0]&0x80)dataSize++;
		dataSize+=1+calcuateSizeOfSizeData(e_size)+e_size;
		if(((unsigned char*)e)[0]&0x80)dataSize++;
		for(i=0;i<6;i++) {
			dataSize+=1+calcuateSizeOfSizeData(sizes[i])+sizes[i];
			if(((unsigned char*)dats[i])[0]&0x80)dataSize++;
		}
		writeSizeDataToBase64(&b64,dataSize);
		writeIntegerToBase64(&b64,(void*)"\x00",1,1);
		writeIntegerToBase64(&b64,n_dat,n_size,1);
		writeIntegerToBase64(&b64,e_dat,e_size,1);
		for(i=0;i<6;i++)writeIntegerToBase64(&b64,dats[i],sizes[i],1);
		base64end(&b64);
		fputs("\n-----END RSA PRIVATE KEY-----\n",fp);
		fclose(fp);
	} else {
		fputs("Private key file open error!\n",stderr);
	}
	/* 解放して終了 */
	free(n_dat);
	free(e_dat);
	for(i=0;i<6;i++)free(dats[i]);
	gmp_randclear(rs);
	mpz_clears(n,e,d,p,q,x1,x2,x3,tmp,NULL);
	return 0;
}

コマンドラインで「使用する素数の」ビット数、公開鍵ファイル、秘密鍵ファイルを指定して実行し、
しばらく待つと名状しがたいSSH鍵のようなものが生成されます。
セキュリティの強度はどうかわかりませんが、VineLinuxとTeraTermを利用した認証の実験には成功しました。

…というわけで、次の目標はこれをJavaScriptに移植することですかね…
JavaScriptに移植すればwebブラウザ上で実行できるだけでなく、サクラエディタのマクロにも乗せられます。
しかし、JavaScriptではGMPは使えない_[要出典]ので、自分で多倍長計算を実装しないといけません。
まあ、それはそのうちに。

Poco · 投稿記事 by **Poco** » 11年前

みけCAT さんが書きました:
CODE:
0x30 (形式情報？例えばBMPファイルなら"BM"みたいなやつ？)
これ以降のデータサイズ
0x02 0x01 0x00 (よくわからない)
0x02 nのデータ
0x02 eのデータ
(0x02 何かの整数のデータ)×6個
のような形式になっていました。
「何かの整数のデータ」は、nやeのデータと同じような形式だったので、整数と予想できました。

多分、ASN.1とかBERとか言われる符号化方式かと。

		7月 2025
日	月	火	水	木	金	土
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

SSHの鍵を作ってみた

SSHの鍵を作ってみた

RE: SSHの鍵を作ってみた