nptclのブログ

Common Lisp処理系nptの開発メモです。https://github.com/nptcl/npt

C言語で楕円曲線DSAを実装する

C言語 Common Lisp

タイトルの通りC言語で楕円曲線DSAを作りました。

https://github.com/nptcl/fixed

作成した曲線は次の通り。

  • secp256k1
  • secp256r1
  • ed25519
  • ed448

Cのサンプルコードみたいな扱いだと思ってください。

以前、Common Lispで作成したもをそのままC言語にしています。
シリーズものですので、よろしかったらどうぞ。

Common Lispで楕円曲線DSAを実装する1 - nptclのブログ
Common Lispで楕円曲線DSAを実装する2（加算） - nptclのブログ
Common Lispで楕円曲線DSAを実装する3（乗算など） - nptclのブログ
Common Lispで楕円曲線DSAを実装する4（確認） - nptclのブログ
Common Lispで楕円曲線DSAを実装する5（鍵生成） - nptclのブログ
Common Lispで楕円曲線DSAを実装する6（署名） - nptclのブログ

コンパイルはたぶん簡単にできます。

$ make

あるいは、

$ cc *.c

で行けると思います。

乱数の初期化に/dev/randomを用いるので、 安全に実行したいならFreeBSDかLinux上で実行してください。
一応コンパイルオプションもあります。

$ cc *.c -DFIXED_FREEBSD
$ cc *.c -DFIXED_LINUX

実行すると次のような出力が出ます。

$ ./a.out
*** RSA
....
make_prime: 3
..
make_prime: 1
e: 10001
d: 9FFD3DDCA87DB013AD4163DBD671EF0FC12C46DD31D498315352511390CF8141
n: EEA9EA825D6BDE300EC2A44B8E2C4863AFF28B4ED97BEB34CBAEA1282F56ACE5
p: FA6A10ED0E527D2D5FEA69D823E22055
q: F3FCC03A690A91D03ADCB175C80AAA51
x1: 10
x2: 20
x3: 30
x4: 40
x5: 50
x1.encode: 7C09DE52BE6CDB831CE4718F524E46D338BDBD43D975794AA45860A8D0033436
x2.encode: 2A70611168D18974D12BDB03170BFFD0C9BB42D4016691C4EBAC8CCC122B2ECE
x3.encode: B76B913220960CD7F46940EFB5EFC354B43931CD102C8E11AEDB6E520D4A4275
x4.encode: C0BD68E1C79F60451B5B7A40245B8E793861B682372B365AA776AD6A12E835F
x5.encode: 5F78B535002AE5741BC650F52E22753B8A804F0DE1C590B1A4DECDCDF0A0FC18
x1.decode: 10
x2.decode: 20
x3.decode: 30
x4.decode: 40
x5.decode: 50


*** ECDSA, EdDSA
[private]
secp256k1: "AE988C663941C1BF51CF6FB9389B4ED787D65F33C5B2113F9B841C7F476FE501"
secp256r1: "C7A31EFEC292540504DD7BB2EC17AD5EA00D922AC628B9FD49F5C14C705F84B5"
ed25519  : "8ED9CDAB174D36EF6ABCC187F3EA4A92F390FB3543B180F2880E2659027BE2FF"
ed448    : "0C69F9CFFD0DED14D73A27AE7B31EC440F0E19FE2AD2D2E1B1D959493BB92ED79C08514EEA26752E182012538C21FDA59C45F10A093F222055"

[public]
secp256k1: "0395BD4A04A9FF7AE239FA42B7BA66B2E38E169DCA699AA1E25F6BAD2E5CDBBD33"
secp256r1: "0380FF1091B9436ED1D170B6E0B5F55C52A0525C61C2A487237FEB4AA7149C92A8"
ed25519  : "709F64FD1AC8DD64E5ADDEED6B6172B31D8BF0B589F303ED831FDF853D2C49CB"
ed448    : "27A40DA2BCAE9DCB16151162A8A652137C5C60B56A7BDFD63568AA68831335509D11EAAA131A9C324E95868F870CA0FCE685896BC49E97F000"

[sign] "Hello"
secp256k1.r: "57861B1A29BEB58F52596ABB825B8D3A8BAA638D70A8A5FAC0AA7ABEC16E443E"
secp256k1.s: "61711E5C9354B0113CB1290FB70D24112133038C2BDCE3DC911BAC03C1FB7186"
secp256r1.r: "D647CC95D5658F2AF8408CCE2A1869B4F7F0BD37FE7018DE67C8A9D6BCB68059"
secp256r1.s: "896B2F320EEB0ED2A0E079C215929E5B4E22D07FBD769338046F48C7CCFB50A2"
ed25519.r  : "77AEAFEB4D363B39D71B19A1C9585E78B6DCE1AC73F2EF01BA77E8AF67878B67"
ed25519.s  : "8DF76ADE07066909794E4F603CF8B3A1A12FC9437C868BD970713C7EC2E1B20D"
ed448.r    : "B694F15A8E7F5BFFE134876BEB8E4DE9F47CEB1F299174C1912FE940C6AF8A3908401AB65248E89F0A4C722468C4E508B6141E83C3DF5E5E80"
ed448.s    : "ED6956E23BCB50F5A611343F548EF5065758EF4B1E3F6AF42E6C15130ABF4B783F6459CFCA69004AFFFDAC8348B4D50338BFB0624E6C101100"

[verify]
secp256k1: T
secp256r1: T
ed25519  : T
ed448    : T

前半の*** RSAと、後半の*** ECDSA, EdDSAで別物です。
前半のRSAは以前記事で書きましたが、 巨大な素数を作って暗号・復号しています。

後半のECDSA, EdDSAは楕円曲線の 秘密鍵、公開鍵、あと"Hello"の署名と検証を行っています。
もし鍵を生成したいなら適当にどうぞ。

作った内容はCommon Lisp版と全く同じです。
C言語版では、鍵生成から署名、検証まで、 全部文字列だけでなんとなかるのが面白かったです。
例えば秘密鍵と公開鍵の生成は次のようになります。

#include "elliptic.h"
#include "random.h"
#include "signature.h"
#include <stdio.h>

int main(void)
{
    char private_key[200];
    char public_key[200];

    init_fixrandom();
    init_elliptic();
    private_string_secp256k1(private_key);
    public_string_secp256k1(private_key, public_key);
    printf("%s\n", private_key);
    printf("%s\n", public_key);

    return 0;
}

実行結果は下記の通り（一例）

E6BD585DCFB42001FD3DDBB0D53D7E1797210DF692567388A0D86D85571E7491
0322703DCC45AD4FBF96D04F662B82B1810B0A1C3E7D233BF570F3CFEC61B840B0

今回は配布物はなんの外部モジュールも必要とせず、 これ単体だけで動作するようになっています。
言い換えるならば必要なものは全部自分で作っています。
なので、副産物としていろいろできたので紹介しておきます。

  • fixed.c, fixed.h

    • bignumの固定長版、例えば1024bit固定の整数演算ができる
    • スタンドアローンで動作可能
    • 本当はこれが主役

  • random.c, random.h

  • sha.c, sha.h

  • sha.lisp

  • elliptic.lisp

    • ECDSA, EdDSAのCommon Lisp版
    • sha.lispだけに依存している

あと、今回せっかく苦労して作ったので、 楕円曲線DSAのマイ公開鍵を公開しておきます。
それに何の意味があるのかはわかりませんが。

  • secp256k1
    • 03FEEF09658067CFBE3BE8685DDCE8E9C03B4A397ADC4A0255CE0B29FC63BCDC9C
  • secp256r1
    • 03CD92CF7B1C9CE9858383806B8540D72FB022BE577E21DE02B8EAA27371DB7AF2
  • ed25519
    • 75AB16F53A060E7AF9A4B8ECEA3D4DEF058AED2C626FEC96D5505C4A7D922960
  • ed448
    • 99AFC3768EE41B96F208EBAF8627908690DC6A5AC64659F93D0A46C2092B61E84AD14DD03F7B3F146799C29F65682126D517B7E1EA57716E00

これであってるのかな。
全然違ってたら悲しい。