ECDSA
ANSI X9.62
IEEE 1363, 1363A
ITU-T X.894 ASN.1 型など
EC なDSA、DSAの後継?乱数は使用する。乱数を使わないらしい EdDSAや確定的ECDSAを使った方がいいようだ 暗号化には利用できない(ECDHなどの鍵交換を利用する)
KT-I など
RFC 5915 秘密鍵の型式
RFC 5480 2.2 公開鍵, 署名などの型式
RFC 4754 RFC 4754 IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)
KT-I と同じ?
TEST Vector
ECDSAは有限体の中で楕円曲線演算を行う
素数を元にした有限体の中で群演算のGF(p)が一般的。secp や P-がつくグループ
AESでおなじみ? ガロア拡大体? GF(2^n)もあるよ。sect やB-, K-のつくグループ?
ということで式も素数を使うsecp(P系)と拡大体を使うsect(B系)の2種類ぐらいある。BはさらにKにも分かれるが式などは同じ?
ECDSA以外だともっと多い。
鍵交換(ECDHE, ECDH)、署名に使われる? 直接暗号には使えないのでECDHを使おう。 DSAの$ g^k を楕円の関数 (ECDSAではkG, EdDSAでは [k]B) っぽく置き換えたもの
離散対数問題(DLP)を楕円曲線上の離散対数問題(ECDLP)に置き換え
table:比較
DSA ECDSA EdDSA ECDH
secp系 sect系 Ed25519 Ed448 Curve25519 Curve448
bit 1024 - 3072 256, 384など 255 448 255 448
y^2≡x^3+ax+b y^2+xy≡x^3+ax^2+b -x^2+y^2≡1+dx^2y^2 x^2+y^2≡1+dx^2y^2 v^2≡u^3+Au^2+u v^2≡u^3+Au^2+u
p Lbit素数 GF(p) GF(2^n) 2^255 - 19 2^448 - 2^224 - 1 2^255-19 2^448-2^224-1
軸 x? y (xでもよさそう) u u
ab aとb A 486662 A 156326
q
g 1 < g < p G B B U(P) 9 U(P) 5
EdDSAはGF(p)
ECDSA
secp 素数 GF(p) と sect ビット GF(2^n)がある
k1で終わる名前の曲線はKobitz曲線といわれている a が0?
EdDSAはハッシュ関数込み, ECDSAは長さに合わせて指定したりいろいろ
曲線
曲線のパラメータ (Fp) $ y^2=x^3+ax^2+b ( mod p)
p prime
a
b
G x, y xは p-3ぐらいが多い?
n order n*G でもとに戻る?
h cofactor p/n の参考値ぐらいの値 標準の曲線では1に近め
基本的にはこの7つとハッシュ関数。Gは始点 hはなくてもいいかも 標準の楕円曲線はほぼ1
秘密鍵
d またはS ?
公開鍵
Y(x, y) = dG
RFC 6090 5.4 KT-I の署名と検証
署名 KT-I という型式
q = order (pではない)
メッセージのハッシュ H(m)
k 乱数 1 <= k < q
R = (Rx, Ry) = kG
s1 = Rx mod q
s2 = (h(m) + 秘密鍵 * s1)/k mod q
s1 = 0 または s2 = 0 のとき k から再度やりなおし
署名 (s1, s2)
検証
q = order
0< s1 < q, 0 < s2 < q の確認
s2_inv = 1/s2 mod q (逆数 s2.modInverse(q))
u1 = h(m) * s2_inv mod q
u2 = s1 * s2_inv mod q
R' = u1G * u2Y
R' mod q と s1 の比較
式
R = kG
s2_inv = k/(h(m) + d * s1)
u1 = k + k/d
R' = (u1 * u2*d)G
鍵の形式
RFC 3279 アルゴリズムと識別子 for the Internet X.509 公開鍵基盤証明書 and Certificate Revocation List (CRL) Profile
ECDSA
RFC 5480 Elliptic Curve Cryptography Subject Public Key Information
公開鍵, 署名
id-ecPublicKey ECDSA無制限鍵(Extensionでのみ限定される)
id-ecDH ECDH/ECDHE?限定鍵
id-ecMQV ECMQV機能限定鍵
RFC 8813 楕円曲線暗号主題公開鍵情報の説明 Clarifications for Elliptic Curve Cryptography Subject Public Key Information
暗号keyUsageの明確な禁止
RFC 5758 署名 ハッシュの追加
SHA-224, SHA-256, SHA-384, SHA-512
RFC 5915 楕円曲線秘密鍵構造 Elliptic Curve Private Key Structure
XML
ECDSAではハッシュが固定ではないので鍵と署名のOIDは別々か?
code:RFC 5915 秘密鍵
ECPrivateKey ::= SEQUENCE {
version INTEGER { ecPrivkeyVer1(1) } (ecPrivateKeyVer1),
privateKey OCTET STRING,
parameters 0 ECParameters {{ NamedCurve }} OPTIONAL, publicKey 1 BIT STRING OPTIONAL }
version 1
parameters RFC 5480で次のような定義↓
code:RFC 5480 ASN
SubjectPublicKeyInfo ::= SEQUENCE {
algorithm AlgorithmIdentifier,
subjectPublicKey BIT STRING
}
AlgorithmIdentifier ::= SEQUENCE {
algorithm OBJECT IDENTIFIER,
parameters ANY DEFINED BY algorithm OPTIONAL
}
id-ecPublicKey OBJECT IDENTIFIER ::= {
iso(1) member-body(2) us(840) ansi-X9-62(10045) keyType(2) 1 }
id-ecDH OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) certicom(132) schemes(1) ecdh(12) }
id-ecMQV OBJECT IDENTIFIER ::= {
iso(1) identified-organization(3) certicom(132) schemes(1) ecmqv(13) }
ECParameters ::= CHOICE {
namedCurve OBJECT IDENTIFIER
-- implicitCurve NULL
-- specifiedCurve SpecifiedECDomain
}
-- implicitCurve および specifiedCurve は PKIX では使用してはいけません（MUST NOT）。
-- SpecifiedECDomain の詳細については X9.62 を参照してください。 -- この CHOICE への将来の追加は、ANSI X9 と調整する必要があります。
ECDSA-Sig-Value ::= SEQUENCE {
r INTEGER,
s INTEGER
}
ECDSAではparametersを使用する
署名型式はJSONなど他の形もあり
RFC 3279 のEckpParametersはRFC 5480で ECParameters, ECParameters はSpecifiedECDomain に変わっているかも code:RFC 3279 2.3.5 ECDSA
EcpkParameters ::= CHOICE {
ecParemeters ECParameters,
namedCurve OBJECT IDENTIFIER,
implicitlyCA NULL }
ECParameters ::= SEQUENCE {
version ECPVer, -- バージョンは常に1
fieldID FieldID, -- 曲線が定義されている有限体(finite field)の識別子
curve Curve, -- 楕円曲線の係数(coefficients) a と b
base ECPoint, -- 楕円曲線上の基点(base point) Pを指定する
order INTEGER, -- 基点の位数 n
cofactor INTEGER OPTIONAL -- 整数 h = #E(Fq)/n }
ECPVer ::= INTEGER {ecpVer1(1)}
Curve ::= SEQUENCE {
a FieldElement,
b FieldElement,
seed BIT STRING OPTIONAL }
FieldElement ::= OCTET STRING
ECPoint ::= OCTET STRING
FieldID ::= SEQUENCE {
fieldType OBJECT IDENTIFIER,
parameters ANY DEFINED BY fieldType }
id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) }
prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 }
Prime-p ::= INTEGER -- Field size p (p in bits)
characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 }
Characteristic-two ::= SEQUENCE {
m INTEGER, -- Field size 2^m
basis OBJECT IDENTIFIER,
parameters ANY DEFINED BY basis }
}
subjectPublicKey が公開鍵
ECPoint ::= OCTET STRING
の形式をbit stringに詰め込む
非圧縮フォーム(MUST)
0x04 x, y
圧縮フォーム(MAY)
0x00 座標0, 0
0x02 -y の圧縮
0x03 +y の圧縮
X9.62のハイブリッド形式(MUST NOT)
使える形式は2種類あり非圧縮が必須、圧縮はあるといい、ハイブリッドは禁止
非圧縮 0x04、圧縮 0x02 または 0x03 ではじめる
証明書の形式
EC汎用のものと、ECDH限定、ECMQV限定のものがある、EC汎用のOIDのものがECDSAで利用できる パラメータで曲線の種類等を指定する
digitalSignature (CA, nonRepudiation以外の署名)
nonRepudiation 否認防止 名前入り証明書など
keyEncipherment 鍵暗号化 (禁止 RFC 8813)
dataEncipherment データ暗号化 (禁止 RFC 8813)
keyAgreement 鍵交換(CAは非推奨)
cipheronly 暗号化のみ
decipheronly 復号のみ
keyCertSign
cRLSign
End Entity(EE)用KeyUsage
digitalSignature デジタル署名
nonRepudiation 否認防止
keyEncipherment 鍵暗号化 (禁止 RFC 8813)
dataEncipherment データ暗号化 (禁止 RFC 8813)
keyAgreement 鍵交換
cipheronly 暗号化のみ
decipheronly 復号のみ
id-ecDH, id-ecMQVはkeyAgreementのみ
digitalSignature 署名(禁止)
nonRepudiation 否認防止(禁止)
keyTransport(禁止)
keyEncipherment 鍵暗号化 (禁止 RFC 8813)
dataEncipherment データ暗号化 (禁止 RFC 8813)
keyAgreement 鍵交換
cipheronly 暗号化のみ
decipheronly 復号のみ
特定の用途
RFC 3279 Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile
RFC 5758 Internet X.509 Public Key Infrastructure: Additional Algorithms and Identifiers for DSA and ECDSA
code:RFC 3279 ECDSA署名
ansi-X9-62 OBJECT IDENTIFIER ::= {
iso(1) member-body(2) us(840) 10045 }
id-ecSigType OBJECT IDENTIFIER ::= {
ansi-X9-62 signatures(4) }
ecdsa-with-SHA1 OBJECT IDENTIFIER ::= {
id-ecSigType 1 }
code:RFC 5758 署名アルゴリズム SHA2
ecdsa-with-SHA224 OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) ansi-X9-62(10045) signatures(4) ecdsa-with-SHA2(3) 1 }
ecdsa-with-SHA256 OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) ansi-X9-62(10045) signatures(4) ecdsa-with-SHA2(3) 2 }
ecdsa-with-SHA384 OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) ansi-X9-62(10045) signatures(4) ecdsa-with-SHA2(3) 3 }
ecdsa-with-SHA512 OBJECT IDENTIFIER ::= { iso(1) member-body(2) us(840) ansi-X9-62(10045) signatures(4) ecdsa-with-SHA2(3) 4 }
code:RFC 8692 SHAKE128/256
id-ecdsa-with-shake128 OBJECT IDENTIFIER ::= { iso(1) identified-organaization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) algorithms(6) 32 }
id-ecdsa-with-shake256 OBJECT IDENTIFIER ::= { iso(1) identified-organaization(3) dod(6) internet(1) security(5) mechanisms(5) pkix(7) algorithms(6) 33 }
code:RFC 9688
sigAlgs OBJECT IDENTIFIER ::= { joint-iso-itu-t(2) country(16) us(840) organization(1) gov(101) csor(3) nistAlgorithm(4) 3 }
id-ecdsa-sha3-224 OBJECT IDENTIFIER ::= { sigAlgs 9 }
id-ecdsa-sha3-256 OBJECT IDENTIFIER ::= { sigAlgs 10 }
id-ecdsa-sha3-384 OBJECT IDENTIFIER ::= { sigAlgs 11 }
id-ecdsa-sha3-512 OBJECT IDENTIFIER ::= { sigAlgs 12 }
ANS X9.62
NIST SP 800-56A 検証?
RFC 6979 乱数を疑似乱数でどうにかする版DSA, ECDSA Deterministic Usage of the Digital Signature Algorithm (DSA) and Elliptic Curve Digital Signature Algorithm (ECDSA) RFC 6090 楕円曲線暗号アルゴリズムの基礎 Fundamental Elliptic Curve Cryptography Algorithms 楕円曲線, EC Diffie-Hellman, ElGamal RFC 9380 Hashing to Elliptic Curves
RFC 5758 Internet X.509 公開鍵基盤: DSA および ECDSA の追加アルゴリズムと識別子 RFC 5656 Elliptic Curve Algorithm Integration in the Secure Shell Transport Layer
RFC 5639 楕円曲線暗号 (ECC) Brainpool 標準カーブ and Curve Generation (情報提供)
RFC 4754 IKE and IKEv2 Authentication Using the Elliptic Curve Digital Signature Algorithm (ECDSA)
RFC 4492 → 8422 ECC Cipher Suites for TLS Versions 1.2 and Earlier
RFC 4050 Using the Elliptic Curve Signature Algorithm (ECDSA) for XML Digital Signatures
FIPS 186-5 を見てみる
ハッシュ関数のほかXOFのSHAKE128, SHAKE256が使われるらしいのでSHA-3系が必要か対応かどちらか 曲線の種類
接頭
ansiX9
sec (ansiX9とだいたいおなじ)
prime
table:強度
強度 楕円のbit pまたはn? RSA
80bit 160bit以上224bit未満 非推奨 廃止
112bit 224bit以上256bit未満 (P-224, B-233, K-233) 非推奨 2048
128bit 256bit以上384bit未満 (P-256, B-283, K-283, W-25519, Curve25519, EdWards25519) 3072
192bit 384bit以上512bit未満 (P-384, B-409, K-409, W-448, Curve448, EdWards448) 7680
256bit 512bit以上 (P-521,B-571,K-571) 15360
強度128bit以上が推奨値
table:Named Curve
SECG名 sec bit ANSI X9.62名 NIST FIPS186-3 OID (RFC 5480 他)
secp160k1 80 ansix9p160k1 1.3.132.0.9 廃止?
secp192k1 80 ansix9p192k1 1.3.132.0.31 廃止?
secp224k1 112 ansix9p224k1 1.3.132.0.32 廃止?
secp256k1 128 ansix9p256k1 1.3.132.0.10 廃止?
secp112r1 50? - 廃止
secp112r2 - 廃止
secp128r1 64? - 廃止
secp128r2 - 廃止
secp160r1 80 ansix9p160r1 1.3.132.0.8 廃止?
secp160r2 80 ansix9p160r2 1.3.132.0.30 廃止?
secp192r1 80 prime192v1 / ansix9p192r1 P-192 1.2.840.10045.3.1.1 / 1.3.132.0.1 (仮?) 廃止?
prime192v2 1.2.840.10045.3.1.2
prime192v3 1.2.840.10045.3.1.3
secp224r1 112 ansix9p224r1 P-224 1.3.132.0.33 廃止?
prime239v1 1.2.840.10045.3.1.4
prime239v2 1.2.840.10045.3.1.5
prime239v3 1.2.840.10045.3.1.6 廃止?
secp256r1 128 prime256v1 / ansix9p256r1 P-256 1.2.840.10045.3.1.7 / 1.3.132.0.7 (仮?)
secp384r1 192 ansix9p384r1 P-384 1.3.132.0.34
secp521r1 256 ansix9p521r1 P-521 1.3.132.0.35
sect163k1 80 ansix9t163k1 K-163 1.3.132.0.1 廃止?
sect233k1 112 ansix9t233k1 K-244 1.3.132.0.26 廃止?
sect239k1 112 ansix9t239k1 1.3.132.0.3
sect283k1 128 ansix9t283k1 K-283 1.3.132.0.16
sect409k1 192 ansix9t409k1 K-409 1.3.132.0.36
sect571k1 256 ansix9t571k1 K-571 1.3.132.0.38
sect113r1 廃止?
sect113r2 廃止?
sect131r1 廃止?
sect131r2 廃止?
sect163r1 ansix9t163r1 1.3.132.0.2 廃止?
sect163r2 80 ansix9t163r2 B-163 1.3.132.0.15 廃止?
c2pnb163v1 1.2.840.10045.3.0.1
c2pub163v2 1.2.840.10045.3.0.2
c2pub163v3 1.2.840.10045.3.0.3
c2pnb176w1 1.2.840.10045.3.0.4
c2tnb191v1 1.2.840.10045.3.0.5
c2tnb191v2 1.2.840.10045.3.0.6
c2tnb191v3 1.2.840.10045.3.0.7
c2onb191v4 1.2.840.10045.3.0.8
c2onb191v5 1.2.840.10045.3.0.9
sect193r1 ansix9t193r1 1.3.132.0.24 廃止?
sect193r2 ansix9t193r2 1.3.132.0.25 廃止?
c2pnb208w1 1.2.840.10045.3.0.10
sect233r1 112 ansix9t233r1 B-233 1.3.132.0.27 廃止?
c2tnb239v1 1.2.840.10045.3.0.11
c2tnb239v2 1.2.840.10045.3.0.12
c2tnb239v3 1.2.840.10045.3.0.13
c2onb239v4 1.2.840.10045.3.0.14
c2onb239v5 1.2.840.10045.3.0.15
c2pnb272w1 1.2.840.10045.3.0.16
sect283r1 128 ansix9t283r1 B-283 1.3.132.0.17
c2pnb304w1 1.2.840.10045.3.0.17
c2tnb359v1 1.2.840.10045.3.0.18
c2pnb368w1 1.2.840.10045.3.0.19
sect409r1 192 ansix9t409r1 B-409 1.3.132.0.37
c2tnb431r1 1.2.840.10045.3.0.20
sect571r1 256 ansix9t571r1 B-571 1.3.132.0.39
ansi名はx9を省略する場合もある ansip256k1など
他に中国のSM2 (256bit)など
標準的な楕円曲線はP-192,P-224,P-256,P-384,P-521 がついているprime192v1, secp224r1, prime256v1, secp384r1, secp521r1
ビットコインではsecp256k1
OpenSSLでは
SECGのANSI別名が使えない
secp192r1とsecp256r1は prime192v1, prime256v1とOIDが別なので名前が使えないようになっている?
secp 素数によるものGF(p) prime
$ y^2 ≡ x^3 + ax + b
Koblitz (a=0, b素数っぽいもの ビットコインなどで使用されているが、標準では廃止されている?)
$ y^2 = x^3 + b
sect バイナリのGF(2^n) c2
$ y^2+xy ≡ x^3 + ax^2 + b
Koblitz (a = 0または1? b = 0 または 1?)
$ y^2 + xy = x^3 + x^2
$ y^2 + xy = x^3 + 1
$ y^2 + xy = x^3
FIPS の P は 素体GF(p)、B, K は票数2の体GF(2^n)。KはKoblitz曲線
ドメインパラメータ
q フィールドサイズ
FR 基準
a, b
Type 楕円曲線モデル
G = (xG, yG) 基点
n 次数
h 余因子
domain_parameter_seed
n のビット長 セキュリティ強度はn/2くらい
224 - 255
256 - 383
384 - 511
512以上
GF(p) と GF(2) p は奇数の素数
秘密鍵 d 公開鍵 Q
6.2. 秘密鍵/公開鍵
6.2.1. キーペアの生成
付録 A.2.
6.2.2. 鍵ペアの管理
6.3. ECDSAメッセージごとの秘密番号の生成
ハッシュ関数またはXOF
H = Hash(M)
秘密乱数 k
参考
ISO 9796-2 疑似乱数?
対応?
OpenSSL 1.0.0 以降
Java 7以降?