読者です 読者をやめる 読者になる 読者になる

Pari/GPでECDH鍵交換、ECDSA署名をやってみる

Crypto

TLS 1.2では、楕円曲線暗号であるECDH鍵交換、ECDSA署名を使うことができる。 ここでは、数式処理システムPari/GPを使ってこれらの計算をやってみる。

環境

Ubuntu 14.04.4 LTS 64bit版、Pari/GP 2.5.5

$ uname -a
Linux vm-ubuntu64 3.19.0-25-generic #26~14.04.1-Ubuntu SMP Fri Jul 24 21:16:20 UTC 2015 x86_64 x86_64 x86_64 GNU/Linux

$ lsb_release -a
No LSB modules are available.
Distributor ID: Ubuntu
Description:    Ubuntu 14.04.4 LTS
Release:        14.04
Codename:       trusty

$ gp --version-short
2.5.5

ECDH、ECDSAが使われている通信を見てみる

一例として、GoogleへのTLS通信では現時点でECDH、ECDSAが使われている。 実際に通信をWiresharkで確認した結果を次に示す。

Frame 31: 1294 bytes on wire (10352 bits), 1294 bytes captured (10352 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Server Hello
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 76
        Handshake Protocol: Server Hello
            Handshake Type: Server Hello (2)
            Length: 72
            Version: TLS 1.2 (0x0303)
            Random
            Session ID Length: 0
            Cipher Suite: TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 (0xc02b)
            Compression Method: null (0)
            Extensions Length: 32
            Extension: renegotiation_info
            Extension: server_name
            Extension: Extended Master Secret
            Extension: SessionTicket TLS
            Extension: Application Layer Protocol Negotiation
            Extension: ec_point_formats

Frame 35: 401 bytes on wire (3208 bits), 401 bytes captured (3208 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Certificate
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 3739
        Handshake Protocol: Certificate
            Handshake Type: Certificate (11)
            Length: 3735
            Certificates Length: 3732
            Certificates (3732 bytes)
                Certificate Length: 1814
                Certificate: 30820712308205faa00302010202082e7dfcf07569326730... (id-at-commonName=*.google.com,id-at-organizationName=Google Inc,id-at-localityName=Mountain View,id-at-stateOrProvinceName=California,id-at-countryName=US)
                    signedCertificate
                        version: v3 (2)
                        serialNumber: 3350111807525696103
                        signature (sha256WithRSAEncryption)
                        issuer: rdnSequence (0)
                        validity
                        subject: rdnSequence (0)
                        subjectPublicKeyInfo
                            algorithm (id-ecPublicKey)
                                Algorithm Id: 1.2.840.10045.2.1 (id-ecPublicKey)
                                ECParameters: namedCurve (0)
                                    namedCurve: 1.2.840.10045.3.1.7 (secp256r1)
                            Padding: 0
                            subjectPublicKey: 041094b0ae65b5baa7e408de4694ca8fcb7275db3a2c3722...
                        extensions: 9 items
                    algorithmIdentifier (sha256WithRSAEncryption)
                    Padding: 0
                    encrypted: 35bb7787aa57a4981d93b867e05e1e04c7030d051803f818...
                Certificate Length: 1012
                Certificate: 308203f0308202d8a0030201020203023a92300d06092a86... (id-at-commonName=Google Internet Authority G2,id-at-organizationName=Google Inc,id-at-countryName=US)
                Certificate Length: 897
                Certificate: 3082037d308202e6a003020102020312bbe6300d06092a86... (id-at-commonName=GeoTrust Global CA,id-at-organizationName=GeoTrust Inc.,id-at-countryName=US)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Server Key Exchange
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 148
        Handshake Protocol: Server Key Exchange
            Handshake Type: Server Key Exchange (12)
            Length: 144
            EC Diffie-Hellman Server Params
                Curve Type: named_curve (0x03)
                Named Curve: secp256r1 (0x0017)
                Pubkey Length: 65
                Pubkey: 0480168e3311d4762dad286445c3bafd6f884e14720c882f...
                Signature Hash Algorithm: 0x0603
                    Signature Hash Algorithm Hash: SHA512 (6)
                    Signature Hash Algorithm Signature: ECDSA (3)
                Signature Length: 71
                Signature: 3045022100f0e6e6cfe84c316f6a3b0a66e7250c4610f3e8...
    TLSv1.2 Record Layer: Handshake Protocol: Server Hello Done

Frame 47: 200 bytes on wire (1600 bits), 200 bytes captured (1600 bits) on interface 0
(snip)
Secure Sockets Layer
    TLSv1.2 Record Layer: Handshake Protocol: Client Key Exchange
        Content Type: Handshake (22)
        Version: TLS 1.2 (0x0303)
        Length: 70
        Handshake Protocol: Client Key Exchange
            Handshake Type: Client Key Exchange (16)
            Length: 66
            EC Diffie-Hellman Client Params
                Pubkey Length: 65
                Pubkey: 0450324b47117a7e0b967e798b9ce8e4147439e403d36191...
    TLSv1.2 Record Layer: Change Cipher Spec Protocol: Change Cipher Spec
    TLSv1.2 Record Layer: Handshake Protocol: Multiple Handshake Messages

上の結果から、CipherSuiteとしてTLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256が選ばれていることがわかる。 そして、サーバ証明書には楕円曲線パラメータsecp256r1でのECDSA用公開鍵が記されており、secp256r1でのECDH用公開鍵がECDSAで署名されていることがわかる。

なお、RFC 4492ではECDHE_ECDSAを用いる場合、サーバ証明書もECDSAで署名されていなければならない(MUST)と記されているが、上の結果ではRSAで署名されているようである。

Pari/GPのインストール

楕円曲線暗号は、ざっくり言うと、素数pを法とする楕円曲線上で定義された定数倍の逆演算が計算量的に困難であること(楕円曲線上の離散対数問題)をもとにした暗号の総称である。 すなわち、ある点Pをd倍した点Qは計算できるが、定数dと点Qから点Pを逆算することが困難であるという性質をもとにしたものである。 RSA暗号において有限体上でe乗した値の逆算が困難であること(離散対数問題)を、楕円曲線上での演算に置き換えたものと考えてもよい。 楕円曲線上で定義された演算の詳細については、Wikipedia等を参照されたい。

楕円曲線上での演算を行うために、ここでは数式処理システムPari/GPを用いることにする。 Pari/GPは次のようにしてインストールできる。

$ sudo apt-get install pari-gp

ECDH鍵交換をやってみる

ECDH鍵交換は、有限体上でのDiffee-Hellman鍵交換を楕円曲線上の演算に置き換えたものである。 Wikipediaを参考に、楕円曲線パラメータsecp256r1で定義される楕円曲線上でのECDH鍵交換を計算してみると次のようになる。

\\ http://pari.math.u-bordeaux.fr/faq.html#hexa
hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}

\\ secp256r1 parameters
\\ http://www.secg.org/sec1-v2.pdf
\\ http://www.secg.org/sec2-v2.pdf
p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
G = [Gx, Gy]
n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")

\\ secp256r1 curve
E = ellinit([0, 0, 0, a, b] * Mod(1, p))
\\ secret key
da = random(n)
db = random(n)
\\ public key
Qa = ellpow(E, G, da)
Qb = ellpow(E, G, db)

\\ calculate shared secret
Xa = lift(ellpow(E, Qb, da))[1]
Xb = lift(ellpow(E, Qa, db))[1]
Xa == Xb

上のコードでは、AとBが互いの公開鍵Qa、Qbを交換し、それぞれの秘密鍵と掛け合わせることで共通鍵Xa == Xbを計算している。 ここで、lift関数はMod(a,b) => aを求める関数である。

実際に実行すると、次のようになる。

$ gp -q
? \\ http://pari.math.u-bordeaux.fr/faq.html#hexa
? hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}
?
? \\ secp256r1 parameters
? \\ http://www.secg.org/sec1-v2.pdf
? \\ http://www.secg.org/sec2-v2.pdf
? p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
115792089210356248762697446949407573530086143415290314195533631308867097853951
? a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
115792089210356248762697446949407573530086143415290314195533631308867097853948
? b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
41058363725152142129326129780047268409114441015993725554835256314039467401291
? Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
48439561293906451759052585252797914202762949526041747995844080717082404635286
? Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
36134250956749795798585127919587881956611106672985015071877198253568414405109
? G = [Gx, Gy]
[48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109]
? n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")
115792089210356248762697446949407573529996955224135760342422259061068512044369
?
? \\ secp256r1 curve
? E = ellinit([0, 0, 0, a, b] * Mod(1, p))
[Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853948, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(41058363725152142129326129780047268409114441015993725554835256314039467401291, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853945, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(48441365690252319754607072170781500106371620648684588023807393947290771751213, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853942, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(144, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(73745129047917570410340083507285168261568990675547578651163356492099206447533, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(47064476442213300654454205837611899485069387829947879813735601543372794627813, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(7958909377132088453074743217357398615041065282494610304372115906626967530147, 115792089210356248762697446949407573530086143415290314195533631308867097853951), 0, 0, 0, 0, 0, 0]
? \\ secret key
? da = random(n)
41624337018869194729192205381537838788846303834619688597471765238035829032504
? db = random(n)
112889434785065900135211481371037383646282385554418514861667765615237067913479
? \\ public key
? Qa = ellpow(E, G, da)
[Mod(66427298351632458827230541581873808673432665230371912577791853634759425959558, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(1206785862317786198788010821239105192836149114902459754806002568469592604088, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
? Qb = ellpow(E, G, db)
[Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(40767119766631682297642348857294685404708822382670655743751860183794421610264, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
?
? \\ calculate shared secret
? Xa = lift(ellpow(E, Qb, da))[1]
55382482432028264043275192986018530076536941443548819581226267882802812179275
? Xb = lift(ellpow(E, Qa, db))[1]
55382482432028264043275192986018530076536941443548819581226267882802812179275
? Xa == Xb
1

XaとXbが同じ値となり、共通鍵を共有できていることが確認できる。

ECDSA署名をやってみる

ECDSA署名は、有限体上でのDSA署名を楕円曲線上の演算に置き換えたものである。 Wikipediaを参考に、楕円曲線パラメータsecp256r1で定義される楕円曲線上でのECDSA署名を計算してみると次のようになる。

\\ http://pari.math.u-bordeaux.fr/faq.html#hexa
hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}

\\ secp256r1 parameters
\\ http://www.secg.org/sec1-v2.pdf
\\ http://www.secg.org/sec2-v2.pdf
p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
G = [Gx, Gy]
n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")

\\ secp256r1 curve
E = ellinit([0, 0, 0, a, b] * Mod(1, p))
\\ secret key
d = random(n)
\\ public key
Q = ellpow(E, G, d)

\\ SHA-512 hash value
z = hextodec("cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e")
z = z >> 256  \\ leftmost 256 bits

\\ sign
k = random(n)
X = lift(ellpow(E, G, k))
r = Mod(X[1], n)
s = Mod((z + r * d)/k, n)
S = lift([r, s])  \\ signature

\\ verify
r = S[1]
s = S[2]
w = Mod(1, n)/s
u1 = lift(z * w)
u2 = lift(r * w)
X = elladd(E, ellpow(E, G, u1), ellpow(E, Q, u2))
r == lift(X[1])  \\ verification result

上のコードでは、秘密鍵dと公開鍵Qの組を用いて、dでSHA-512ハッシュ値zに対する署名Sを生成した後、zとQでこの署名Sの検証を行っている。 ここで、SHA-512ハッシュ値は512bitであるが、署名を計算する際には上位256bit(楕円曲線パラメータのnのbit数)が取り出されて用いられる。

実際に実行すると、次のようになる。

$ gp -q
? \\ http://pari.math.u-bordeaux.fr/faq.html#hexa
? hextodec(s) =
{ my(v=Vec(s), a=10,b=11,c=12,d=13,e=14,f=15,
               A=10,B=11,C=12,D=13,E=14,F=15, h);

  for(i=1,#v,h = (h<<4) + eval(v[i])); h;
}
?
? \\ secp256r1 parameters
? \\ http://www.secg.org/sec1-v2.pdf
? \\ http://www.secg.org/sec2-v2.pdf
? p = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF")
115792089210356248762697446949407573530086143415290314195533631308867097853951
? a = hextodec("FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC")
115792089210356248762697446949407573530086143415290314195533631308867097853948
? b = hextodec("5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B")
41058363725152142129326129780047268409114441015993725554835256314039467401291
? Gx = hextodec("6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296")
48439561293906451759052585252797914202762949526041747995844080717082404635286
? Gy = hextodec("4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5")
36134250956749795798585127919587881956611106672985015071877198253568414405109
? G = [Gx, Gy]
[48439561293906451759052585252797914202762949526041747995844080717082404635286, 36134250956749795798585127919587881956611106672985015071877198253568414405109]
? n = hextodec("FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551")
115792089210356248762697446949407573529996955224135760342422259061068512044369
?
? \\ secp256r1 curve
? E = ellinit([0, 0, 0, a, b] * Mod(1, p))
[Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853948, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(41058363725152142129326129780047268409114441015993725554835256314039467401291, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(0, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853945, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(48441365690252319754607072170781500106371620648684588023807393947290771751213, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(115792089210356248762697446949407573530086143415290314195533631308867097853942, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(144, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(73745129047917570410340083507285168261568990675547578651163356492099206447533, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(47064476442213300654454205837611899485069387829947879813735601543372794627813, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(7958909377132088453074743217357398615041065282494610304372115906626967530147, 115792089210356248762697446949407573530086143415290314195533631308867097853951), 0, 0, 0, 0, 0, 0]
? \\ secret key
? d = random(n)
41624337018869194729192205381537838788846303834619688597471765238035829032504
? \\ public key
? Q = ellpow(E, G, d)
[Mod(66427298351632458827230541581873808673432665230371912577791853634759425959558, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(1206785862317786198788010821239105192836149114902459754806002568469592604088, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
?
? \\ SHA-512 hash value
? z = hextodec("cf83e1357eefb8bdf1542850d66d8007d620e4050b5715dc83f4a921d36ce9ce47d0d13c5d85f2b0ff8318d2877eec2f63b931bd47417a81a538327af927da3e")
10868450558671247443152026947160338505683745266658651051718065983487878962987857602829315249215796444208488632888003673539585986066311769564391053988452926
? z = z >> 256  \\ leftmost 256 bits
93861770957395276492717477787726143810336548400896766194917568669650606942670
?
? \\ sign
? k = random(n)
112889434785065900135211481371037383646282385554418514861667765615237067913479
? X = lift(ellpow(E, G, k))
[45117477251749228939119226983445827678526666004268395927426481263854185200718, 40767119766631682297642348857294685404708822382670655743751860183794421610264]
? r = Mod(X[1], n)
Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? s = Mod((z + r * d)/k, n)
Mod(19480684571390165669037418791352587666543987715102909683921619662453630129808, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? S = lift([r, s])  \\ signature
[45117477251749228939119226983445827678526666004268395927426481263854185200718, 19480684571390165669037418791352587666543987715102909683921619662453630129808]
?
? \\ verify
? r = S[1]
45117477251749228939119226983445827678526666004268395927426481263854185200718
? s = S[2]
19480684571390165669037418791352587666543987715102909683921619662453630129808
? w = Mod(1, n)/s
Mod(45806731425320108599593801776916401592588010577151454492237521859734605583062, 115792089210356248762697446949407573529996955224135760342422259061068512044369)
? u1 = lift(z * w)
2526355770588513432897987911358560530387299975513306266181348358497798666960
? u2 = lift(r * w)
39403108001448584892010322851840404729316330706803748468373485665520707319225
? X = elladd(E, ellpow(E, G, u1), ellpow(E, Q, u2))
[Mod(45117477251749228939119226983445827678526666004268395927426481263854185200718, 115792089210356248762697446949407573530086143415290314195533631308867097853951), Mod(40767119766631682297642348857294685404708822382670655743751860183794421610264, 115792089210356248762697446949407573530086143415290314195533631308867097853951)]
? r == lift(X[1])  \\ verification result
1

上の結果から、秘密鍵dで計算されたハッシュ値zに対する署名Sを、zと公開鍵Qで検証できていることが確認できる。

関連リンク