PSEC-KEM 仕様書
version 2.2
日本電信電話株式会社
NTT 情報流通プラットフォーム研究所
平成 20 年 4 月 14 日

更新履歴version 2.2

2008/4/14

version 1.1
version 1.0

2002/5/14
2001/9/26

3 章のコンバージョン関数と 1 章,3 章,5 章の修正および
誤字脱字の修正.(英語版 version2.2 に対応する修正)
付録および誤字脱字の修正.(英語版 version2.1 に対応する修正)
ハッシュ関数に SHA-1, SHA-224, SHA-256, SHA-384, SHA-512を追加.(英語版 version2.01 に対応する修正)
ISO/IEC 18033-2 準拠となるように修正 (英語版 version2.0 に対応する修正)3 章のコンバージョンの修正および誤字脱字の修正.

2

目次
1

はじめに

4

2

記法
2.1 記法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 楕円曲線パラメータ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4
4
4

3

データ型および型変換
3.1 整数からビット列への変換 (I2BSP) . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 ビット列から整数への変換 (BS2IP) . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 ビット列からオクテット列への変換 (BS2OSP) . . . . . . . . . . . . . . . . . . . .
3.4 オクテット列からビット列への変換 (OS2BSP) . . . . . . . . . . . . . . . . . . . .
3.5 整数からオクテット列への変換 (I2OSP) . . . . . . . . . . . . . . . . . . . . . . .
3.6 オクテット列から整数への変換 (OS2IP) . . . . . . . . . . . . . . . . . . . . . . .
3.7 有限体の元から整数への変換 (FE2IP) . . . . . . . . . . . . . . . . . . . . . . . . .
3.8 整数から有限体の元への変換 (I2FEP) . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 有限体の要素からオクテット列への変換 (FE2OSP) . . . . . . . . . . . . . . . . .
3.10 オクテット列から有限体の要素への変換 (OS2FEP) . . . . . . . . . . . . . . . . .
3.11 楕円曲線上の点からオクテット列への変換 (ECP2OSP) . . . . . . . . . . . . . . .
3.12 オクテット列から楕円曲線上の点への変換 (OS2ECPP) . . . . . . . . . . . . . . .
3.13 楕円曲線上の点の部分情報からオクテット列への変換 (PECP2OSP) . . . . . . . .

5
5
6
7
8
8
8
9
9
10
11
11
12
14

4

システムパラメータ・秘密鍵・公開鍵
4.1 PSEC-KEM システムパラメータ . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 PSEC-KEM 秘密鍵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 PSEC-KEM 公開鍵 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14
14
14
14

5

鍵カプセル化メカニズム PSEC-KEM
5.1 鍵生成処理 (KGP-PSEC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 鍵カプセル化メカニズム (ES-PSEC-KEM) . . . . . . . . . . . . . . . . . . . . . .
5.2.1 暗号化処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 復号処理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15
15
15
15
16

6

補助関数
6.1 ハッシュ関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 鍵導出関数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1 MGF1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16
16
16
17

A パラメータ設定基準

18

B パラメータ推奨値

18

C ASN.1 Syntax

18

3

1

はじめに

本仕様は , 鍵カプセル化メカニズム PSEC-KEM の仕様である. 鍵カプセル化メカニズム (KEM)
は , 対称暗号技術で用いる鍵を暗号化するための非対称暗号技術である. このような対象暗号技術をデータカプセル化メカニズム (DEM) と呼ぶ. KEM と DEM を組み合わせることを KEM-DEM
フレームワークと呼び , 非対称ハイブリッド 暗号を実現することができる. これらの技術の定義および使用法に関しては ISO/IEC 18033-2 [1] の 8 章を参照のこと .
本仕様に基づいた PSEC-KEM の実装は ISO/IEC 18033-2 [1] で規定される PSEC-KEM に準拠している.

2

記法

2.1

記法

ビット
ビット列
オクテット
オクテット列RZ
N
a := b
Fqm
O
k
⊕
dye
byc
a|b
a mod ma−1 mod m

2.20 または 1 のシンボル
ビットが並べられた列長さ 8 のビット列
オクテットが並べられた列
実数の集合
整数の集合
正の整数の集合b の値を a に代入する. または， a は b で定義される.
要素数 q m の有限体. q は素数.
楕円曲線上の無限遠点
ビット列またはオクテット列の連結演算子．この記号は省略されることもある.
ビット毎の排他的論理和
y ∈ R のとき， y 以上の最小の整数.
y ∈ R のとき，y 以下の最大の整数.
a は b を割り切る．つまり， b = ac となる整数 c が存在する.
a ∈ Z, m ∈ N のとき， m|(a − b) なる最小の非負整数 b.
a ∈ Z, m ∈ N のとき， ab mod m = 1 なる最小の非負整数 b.

楕円曲線パラメータ

楕円曲線パラメータ E は九つ組 (q, m, f (β), a, b, P, p, pLen, qmLen) からなる．ここで各構成
要素は以下のものである：• q, 素数. ただし , q 6= 3
• m, 正の整数• f (β), 次数 m の Fq 係数モニック既約多項式, Fqm の定義多項式• a, Fqm の元• b, Fqm の元
4

• P , 楕円曲線上の点 (x, y)– x, Fqm の元– y, Fqm の元
ただし 、x, y は次の式を満たす.
q > 3 のとき : y 2 = x3 + ax + b, ここで 4a3 + 27b2 6= 0.
q = 2 のとき : y 2 + xy = x3 + ax2 + b, ここで b 6= 0.

• p, P の位数, 素数• pLen, dlog256 pe の値• qmLen, dlog256 q m e の値

3

データ型および型変換

本仕様で規定する暗号アルゴ リズムは , 非負整数, 有限体, オクテット列, ビット列, 楕円曲線上の点の 5 つのデータ型に関する演算によって構成されており, しばしばこれらのデータ型の間の型変換を必要とする. 本仕様に準拠する異なる実装がデータ交換を確実に行うためには , これらの型変換の仕様を一意に確定しておく必要がある. 本節ではそれらの型変換の規定を行う. 必要なデー
タ型および型変換の関係を図 1 に示す. 5 つのデータ型はそれぞれ略称, 非負整数 (I), 有限体 (FE),オクテット列 (OS), ビット列 (BS), 楕円曲線上の点 (ECP) を持つ. それぞれの型変換関数の名称
は入力および出力の型の略称の組み合わせにより決定される. 型変換関数によっては補助的な入力が必要な場合がある. 各々の型変換関数に入力定義域外のデータが入力された場合は INVALID
がエラー出力されるとする. 一回の暗号アルゴ リズムの処理内で一度でもエラー出力があった場
合は , エラーを出力した関数の呼び出し元 または より上位のモジュールにて確実に捕捉され , その暗号アルゴ リズムの処理は中断され , 適切な処理が行われる事を意図している.

3.1

整数からビット 列への変換 (I2BSP)

本仕様に基づく実装は , 整数からビット列への変換を実行する際, 以下の関数 I2BSP(x, l) と入出力関係が等価なアルゴ リズムを使用しなくてはならない. この関数は整数を 2 進数で表現する
アルゴ リズムに基づいている. 型変換関数 I2BSP(x, l) は形式的に次の様に定義される:
入力:
出力:
エラー:
処理手順:

x 非負整数l
出力のビット長, 非負整数
B 長さ l のビット列
INVALID

1. もし x ≥ 2l ならば , INVALID をエラー出力し停止する.
2. もし l = 0 ならば , 空のビット列を出力し停止する.
5

'

$

楕円曲線上の点

P = (x, y)
または O
&



ECP2OSP(P, R) OS2ECPP(M )Â¿オクテット列 MÁ%À

Mi はオクテット .

x, y : 有限体の元

Â

オクテット列M = M0 M1 · · · Mn−1

À

6

I2

O
SP
O
(x
S2
,n
IP
)
(M
)


>

 Á

a) 

7
(

SP )2O  M
FE  EP(  2F OS




=


/
'
$
»
FE2IP(a) ¿¼ I2FEP(x)非負整数 x

&

%

x,
P(

l)

)
(B
IP

2
BS

BS
I2

S
oS
SS
SS
SS
SS
SS
SS
w
SS
Â

OS2BSP(M )有限体の元 a½

BS2OSP(B)

¾

?

ビット列
B = B0 B1 · · · Bl−1Á¿ÀBi ∈ {0, 1}
図 1: データ型および型変換の関係

3. 以下を満たす x の 2 進表現 xi ∈ {0, 1} を決定する.
x = xl−1 2l−1 + xl−2 2l−2 + · · · + x1 2 + x0 .
4. i ∈ {0, . . . , l − 1} に関して Bi := xl−1−i とし ,B := B0 B1 · · · Bl−1 .
とする.

5. B を出力する.

3.2

ビット 列から整数への変換 (BS2IP)

本仕様に基づく実装は , ビット列から整数への変換を実行する際, 以下の関数 BS2IP(B) と入出力関係が等価なアルゴ リズムを使用しなくてはならない. この関数はビット列を単に整数の 2 進表
現とみなすアルゴ リズムに基づいている. 型変換関数 BS2IP(B) は形式的に次の様に定義される:

6

入力:
出力:
処理手順:

B
x

長さ l のビット列
非負整数

B = B0 B1 · · · Bl−1 なるビット列 B は以下のように整数 x に変換される:
1. もし l = 0 ならば , 0 を出力して停止する.
2. 各 Bi を 整数 (∈ {0, 1}) とみなし , i ∈ {0, . . . , l − 1} に関して xi := Bi とし ,
x :=

l−1
X

2(l−1−i) xi .

i=0

とする.

3. x を出力する.

3.3

ビット 列からオクテット 列への変換 (BS2OSP)

本仕様に基づく実装は , ビット列からオクテット列への変換を実行する際, 以下の関数 BS2OSP(B)と入出力関係が等価なアルゴ リズムを使用しなくてはならない. この関数はビット列の長さを 8の 倍数とするため 左端を 0 で 埋めるアルゴ リズムに基づいている. 型変換関数 BS2OSP(B) は
形式的に次の様に定義される:
入力:

B

出力:

M

長さ l のビット列» ¼l
長さ n =のオクテット列
8

処理手順:
ビット列 B = B0 B1 · · · Bl−1 をオクテット列 M = M0 M1 · · · Mn−1 へ以下のように変換する:

1. もし l = 0 ならば , 空のオクテット列を出力して停止する.
2. j ∈ {0, . . . , 8n − 1} に関して
(
ej =
B

Bj−(8n−l)0

if j ≥ 8n − l,if j < 8n − l.

とする.

3. i ∈ {0, . . . , n − 1}, に関して
e8i B
e8i+1 · · · B
e8i+7
Mi := Bとする.

4. M を出力する.

7

3.4

オクテット 列からビット 列への変換 (OS2BSP)

本仕様に基づく実装は , オクテット列からビット列への変換を実行する際, 以下の関数 OS2BSP(M )と入出力関係が等価なアルゴ リズムを使用しなくてはならない. この関数はオクテット列を単にビット列とみなすアルゴ リズムに基づいている. 型変換関数 OS2BSP(M ) は形式的に次の様に定
義される:
入力:
出力:
処理手順:

M
B

長さ n のオクテット列
長さ l = 8n のビット列

オクテット列 M = M0 M1 · · · Mn−1 をビット列 B = B0 B1 · · · Bl−1 へ以下のように変換する.

1. もし l = 0 ならば , 空のビット列を出力し停止する.
2. i ∈ {0, . . . , n − 1}, j ∈ {0, . . . , 7} に関して以下を満たす B8i+j ∈ {0, 1} を決定する.
Mi = B8i B8i+1 · · · B8i+7
3. B を出力する.

3.5

整数からオクテット 列への変換 (I2OSP)

本仕様に基づく実装は , 整数からオクテット列への変換を実行する際, 以下の関数 I2OSP(x, n)と入出力関係が等価なアルゴ リズムを使用しなくてはならない. この関数は整数をビット列に変換し , 得られたビット列をオクテット列に変換するアルゴ リズムに基づいている. 型変換関数
I2OSP(x, n) は形式的に次の様に定義される:
入力:
出力:
エラー:
処理手順:

x
非負整数
n
出力のオクテット長.
M 長さ n のオクテット列
INVALID

1. M := BS2OSP(I2BSP(x, 8n)) とする.
2. M を出力する.

3.6オクテット 列から整数への変換 (OS2IP)

本仕様に基づく実装は , オクテット列から整数への変換を実行する際, 以下の関数 OS2IP(M ) と入出力関係が等価なアルゴリズムを使用しなくてはならない. この関数はオクテット列をビット列に変換し , 得られたビット列を整数に変換するアルゴ リズムに基づいている. 型変換関数 OS2IP(M )は形式的に次の様に定義される:
入力:
出力:
処理手順:

M
x

長さ n のオクテット列
非負整数

8

1. x := BS2IP(OS2BSP(M )) とする.
2. x を出力する.

3.7

有限体の元から整数への変換 (FE2IP)

本仕様に基づく実装は , 有限体から整数への変換を実行する際, 以下の関数 FE2IP(a) と入出力関係が等価なアルゴ リズムを使用しなくてはならない. 有限体の元は整数係数多項式の係数の列として表現されているとする. q を有限体の標数として , この関数は係数の列を単に整数の q 進数表
示とみなすアルゴ リズムに基づいている. 型変換関数 FE2IP(a) は形式的に次の様に定義される:システムパラメータ:
入力:
出力:
処理手順:

Fqm
a
x

位数 q m の有限体 (q は素数, m > 0 は整数)
Fqm の元0 以上 q m 未満の整数

有限体の元 a を整数 x に以下のように変換する:

m = 1 の場合:
有限体の元 a は整数 (∈ {0, . . . , q − 1}) として表現されている.
1. x := a とする.
2. x を出力する.
m > 1 の場合:
有限体の元 a は {0, . . . , q − 1} に係数をもつ高々 (m − 1) 次の多項式として表現されている. β をこの多項式の不定元とする.
1. i ∈ {0, . . . , m − 1} に関して以下を満たす係数 ai ∈ {0, . . . , q − 1} を決定
する.
m−1
X
a=
ai β i .
i=0

2. 以下を計算する.
x :=

m−1
X

ai q i .

i=0

3: x を出力する.

3.8

整数から有限体の元への変換 (I2FEP)

本仕様に基づく実装は , 整数から有限体への変換を実行する際, 以下の関数 I2FEP(x) と入出力関係が等価なアルゴ リズムを使用しなくてはならない. 有限体の元は整数係数多項式の係数の列として表現されるとする. q を有限体の標数として , この関数は整数を q 進数表示し , 各桁を多項式の係数とみなすアルゴ リズムに基づいている. 型変換関数 I2FEP(x) は形式的に次の様に定義される:

9

システムパラメータ:
入力:
出力:
処理手順:

Fqm
x
a

位数 q m の有限体 (q は素数, m > 0 は整数)
0 以上 q m 未満の整数
Fqm の元整数 x を有限体の元 a へ以下のように変換する:

m = 1 の場合:
Fqm の元は必ず整数 (∈ {0, . . . , q − 1}) として表現される.
1. a := x とする.
2. a を出力する.
m > 1 の場合:
Fqm の元は必ず {0, . . . , q − 1} に係数をもつ高々 (m − 1) 次の多項式として表現される. β をこの多項式の不定元とする.
1. x を i ∈ {0, . . . , m − 1} に関して以下を満たす q 進表現 xi ∈ {0, . . . , q − 1}に展開する.
m−1
Xx=xi q i .
i=0

2. 以下を計算する.
a :=

m−1
X

xi β i .

i=0

3: a を出力する.

3.9

有限体の要素からオクテット 列への変換 (FE2OSP)型変換関数 FE2OSP(a) は以下のように定義される:システムパラメータ:

Fqm
n

入力:
出力:
処理手順:

a
M

位数
q m の有限体(q は素数, m > 0 は整数)»¼
m log2 qと等しい整数8
Fqm の元オクテット列1.
M := I2OSP(FE2IP(a), n).
とする.

2. M を出力する.
注: システムパラメータは FE2IP と同じ .

10

3.10

オクテット 列から有限体の要素への変換 (OS2FEP)型変換関数 OS2FEP(M ) は以下のように定義される:システムパラメータ:

入力:
出力:
エラー:
処理手順:

位数
q m の有限体(q は素数, m > 0 は整数)»¼
m log2 qnと等しい整数
8
M
オクテット列a
Fqm の元INVALID

Fqm

1.
a := I2FEP(OS2IP(M )).
とする.

2. a を出力する.
注: システムパラメータは I2FEP と同じ .

3.11

楕円曲線上の点からオクテット 列への変換 (ECP2OSP)

楕円曲線上の点からオクテット列への変換方法はおよそ次の通りである.
もし 圧縮フォーマットを用いるなら圧縮を利用する旨の指示と共に 圧縮された y 座標がオク
テット列の先頭オクテットに記録され , その後に x 座標が配置される.
圧縮フォーマットを用いないなら圧縮を利用しない旨の指示をオクテット列の先頭オクテットに配置し , その後に x 座標を配置し , その後に y 座標を配置する.
型変換関数 ECP2OSP(P, R) の詳細は以下の通りである:
システムパラメータ:
入力:
出力:

E
P
R
M

楕円曲線パラメータ
Fqm 上の楕円曲線の点
Compressed または Uncompressed または Hybrid
長さ n のオクテット列(P = O のとき)¼

n = 1»
m log2 qn=+1(P 6= O かつ R が Compressed のとき),
ただし
8
»
¼


m log2 q n=2+ 1 (P =6 O かつ R が Uncompressed または Hybrid のとき)
8
処理手順:
P をオクテット列 M = M0 M1 · · · Mn−1 に以下のように変換する:
1. P = O ならば M := I2OSP(0, 1) を出力する.
2. P = (x, y) 6= O であり, かつ R = Compressed ならば , 次を行う.
2.1. オクテット列 X を X := FE2OSP(x) とする.
2.2. y より 1 ビットの ỹ を以下のように求める (このとき y 座標は 1 ビットに収まる):
11

2.2.1. q が奇素数の場合, y = 0 ならば ỹ := 0 とし , y 6= 0 ならば ỹ := yi mod 2 とする. ただし , y = ym−1 β m−1 + · · · + y1 β + y0 としたときに i は yi 6= 0 を満たす
もっとも小さな整数である.
2.2.2. q = 2 の場合, x = 0 ならば ỹ := 0 とし , そうでなければ z = yx−1 を満たす
z = zm−1 β m−1 + · · · + z1 β + z0 を計算し , ỹ := z0 とする.
2.3. ỹ = 0 ならば I2OSP(2, 1) を L に割り当てる. ỹ = 1 ならば I2OSP(3, 1) を L に割り当てる.
2.4. M := L k X を出力する.
3. P = (x, y) 6= O かつ R = Uncompressed ならば , 次を行う.
3.1. オクテット列 X を X := FE2OSP(x) とする.
3.2. オクテット列 Y を Y := FE2OSP(y) とする.
3.3. M := I2OSP(4, 1) k X k Y を出力する.
4. P = (x, y) 6= O かつ R = Hybrid ならば , 次を行う.
4.1. オクテット列 X を X := FE2OSP(x) とする.
4.2. オクテット列 Y を Y := FE2OSP(y) とする.
4.3. y より 1 ビットの ỹ を以下のように求める (このとき y 座標は 1 ビットに収まる):
4.3.1. q が奇素数の場合, y = 0 ならば ỹ := 0 とし , y 6= 0 ならば ỹ := yi mod 2 とする. ただし , y = ym−1 β m−1 + · · · + y1 β + y0 としたときに i は yi 6= 0 を満たす
もっとも小さな整数である.
4.3.2. q = 2 の場合, x = 0 ならば ỹ := 0 とし , そうでなければ z = yx−1 を満たす
z = zm−1 β m−1 + · · · + z1 β + z0 を計算し , ỹ := z0 とする.
4.4. ỹ = 0 ならば I2OSP(6, 1) を L に割り当てる. ỹ = 1 ならば I2OSP(7, 1) を L に割り当てる.
4.5. M := L k X k Y を出力する.

3.12オクテット 列から楕円曲線上の点への変換 (OS2ECPP)

楕円曲線上の点からオクテット列への変換方法はおよそ次の通りである.
もし圧縮フォーマットが用いられているならオクテット列の先頭に配置されるオクテットより圧縮された y 座標を取り出し , その後に続くオクテット列より x 座標を取り出す. しかる後に 完
全な y 座標を取り出す.
圧縮フォーマットが用いられていないなら先頭のオクテットを削除して続くオクテット列の前半より x 座標を , 後半より y 座標を復元する.
型変換関数 OS2ECPP(M ) の詳細は以下の通りである:12システムパラメータ:
入力:

出力:
エラー:
処理手順:

E
M

楕円曲線パラメータ
以下のいずれかのオクテット列
I2OSP(0,»1) または¼
m log2 q
長さ n =+ 1 のオクテット列または» 8¼
m log2 q
長さ n = 2+ 1 のオクテット列
8P
楕円曲線上の点
INVALID

M を楕円曲線上の点 P に以下のように変換する:
1. M = I2OSP(0, 1), ならば P := O を出力する.
»¼
m log2 q
2. M が長さ+ 1 のオクテット列の場合, 次を行う:
8»m log2 q
2.1. M を M = L k X となるように , 長さ 1 のオクテット L と , 続く長さ
8クテット列 X に分解する.

¼のオ

2.2. x := OS2FEP(X) とする.
2.3. L = I2OSP(2, 1) なら , ỹ := 0 とし , L = I2OSP(3, 1) なら , ỹ := 1 とし , それ以外な
らば INVALID をエラー出力し停止する.
2.4. x と ỹ より楕円曲線上の点 P := (x, y) を以下のように求める:
2.4.1. q が奇素数の場合, Fqm 上の元 w = x3 + ax + b を計算し , w の Fqm 上の平方
根 γ を求める. 平方根が存在しないなら INVALID をエラー出力し 停止する. もし γ = 0 ならば , y = 0 とする. もし γi ≡ ỹ mod 2 ならば y = γ とし , γi 6≡ ỹmod 2 ならば y = −γ とする. ただし , γ = γm−1 β m−1 + · · · + γ1 β + γ0 としたと
きに i は γi 6= 0 を満たすもっとも小さな整数である.
m−1

2.4.2. q = 2 で x = 0 なら , y := b2∈ Fqm とする.

2.4.3. q = 2 で x 6= 0 なら , Fqm 上の元 γ := x + a + bx−2 を計算し , z 2 + z = γ なる Fqm の元 z = zm−1 β m−1 + · · · + z1 β + z0 を求める. もし z が存在しないなら
INVALID をエラー出力し停止する. z0 = ỹ ならば y = xz ∈ Fqm とする. z0 6= ỹ
ならば y = x(z + 1) ∈ Fqm とする.
2.5. P := (x, y) を出力する.
»¼
m log2 q
3. M が長さ 2+ 1 のオクテット列の場合, 次を行う:
8»¼
m log2 q
3.1. M を M = L k X k Y となるように , 長さ 1 のオクテット L と , 続く長さ
8»¼
m log2 qのオクテット列の X と , 続く長さのオクテット列の Y に分解する.
83.2. L = I2OSP(4, 1) または I2OSP(6, 1) または I2OSP(7, 1) であるかど うかを検査す
る. それ以外ならば , INVALID をエラー出力し停止する.
13

3.3. x := OS2FEP(X) とする.
3.4. y := OS2FEP(Y ) とする.
3.5. 点 P := (x, y) が E で定義される楕円曲線の定義方程式を満たさなければ , INVALID
をエラー出力し停止する.
3.6. P := (x, y) を出力する.

3.13

楕円曲線上の点の部分情報からオクテット 列への変換 (PECP2OSP)型変換関数 PECP2OSP(P ) は以下のように定義される:システムパラメータ:
入力:

E
P

出力:

M

楕円曲線パラメータ
Fqm 上の楕円曲線の点»¼m log2 q
長さ n =のオクテット列.
8

処理手順:
楕円曲線上の点 P からオクテット列 M = M0 M1 · · · Mn−1 への変換方法は次の通りである.

1. P = O ならば , M := I2OSP(0, n) を出力する.
2. P = (x, y) 6= O ならば , M := FE2OSP(x) を出力する.

4

システムパラメータ・秘密鍵・公開鍵

4.1

PSEC-KEM システムパラメータ

PSEC-KEM システムパラメータは以下の値からなる.
• E, 2.2 節に記述されている楕円曲線パラメータ• KDF , 6.2 節に記述されている鍵導出関数• hLen, 正の整数
• keyLen, 正の整数

4.2

PSEC-KEM 秘密鍵

PSEC-KEM 秘密鍵は以下の値からなる.
• s, 非負整数 0 ≤ s < p

4.3

PSEC-KEM 公開鍵

PSEC-KEM 公開鍵は以下の値からなる.
• W , 楕円曲線 E 上の点
145

鍵カプセル化メカニズム PSEC-KEM
本章では、以下の 3 つのアルゴ リズムからなる PSEC-KEM について述べる.

• 鍵生成アルゴ リズム KGP-PSEC
入力はなし , 出力は公開鍵と秘密鍵 (W, s).
• 暗号化処理 ES-PSEC-KEM-Encrypt
入力は公開鍵 W とフォーマット R, 出力は鍵と暗号文の対 (k, c0 ).
• 復号処理 ES-PSEC-KEM-Decrypt
入力は秘密鍵 s と暗号文 c0 , 出力は鍵 k.

5.1

鍵生成処理 (KGP-PSEC)KGP-PSEC() は以下のように定義される.
入力:
出力:

W
s

KGP-PSEC は入力を取らない
PSEC-KEM 公開鍵, 楕円曲線 E 上の点
PSEC-KEM 秘密鍵, 非負整数 0 ≤ s < p

処理手順:

1. ランダムな整数 s ∈ {0, · · · , p − 1} を生成する.
2. W := sP とする.
3. W と s を出力する.

5.2
5.2.1

鍵カプセル化メカニズム (ES-PSEC-KEM)
暗号化処理

ES-PSEC-KEM-Encrypt(W, R) は以下のように定義される.
入力:
出力:

W
R
k
c0

PSEC-KEM 公開鍵, 楕円曲線 E 上の点
Compressed または Uncompressed または Hybrid
オクテット列オクテット列処理手順:

1. ランダムな長さ hLen のオクテット列 r を生成する.
2. H := KDF (I2OSP(0, 4) k r, pLen + 16 + keyLen) とする.
3. H = t k k を , 長さ pLen + 16 のオクテット列 t と , 長さ keyLen のオクテット列 k に分解する.
4. α := OS2IP(t) mod p とする.
5. C1 := αP とする.
15

6. Q := αW とする.
7. c2 := r ⊕ KDF (I2OSP(1, 4) k ECP2OSP(C1 , R) k PECP2OSP(Q), hLen) とする.
8. c0 := ECP2OSP(C1 , R) k c2 とする.
9. (k, c0 ) を出力する.
5.2.2

復号処理

ES-PSEC-KEM-Decrypt(s, c0 ) は以下のように定義される.
入力:
出力:
エラー:
処理手順:

s PSEC-KEM 秘密鍵, 非負整数 0 ≤ s < p
c0 オクテット列
k オクテット列
INVALID

1. c0 のオクテット長が hLen 未満ならば , INVALID をエラー出力し停止する.
2. c0 = g k c2 を , オクテット列 g と , 長さ hLen のオクテット列 c2 に分解する.
3. C1 := OS2ECPP(g) とする. OS2ECPP が INVALID をエラー出力したら , INVALID をエラー出力し停止する.
4. Q := sC1 とする.
5. r := c2 ⊕ KDF (I2OSP(1, 4) k g k PECP2OSP(Q), hLen) とする.
6. h := KDF (I2OSP(0, 4) k r, pLen + 16 + keyLen) とする.
7. h = t k k を , 長さ pLen + 16 のオクテット列 t と , 長さ keyLen のオクテット列 k に分解する.
8. α := OS2IP(t) mod p とする.
9. C1 = αP をチェックする. 成立するときは , k を出力しする. そうでなければ , INVALID をエラー出力し停止する.

6

補助関数

6.1

ハッシュ関数許容されるハッシュ関数は , ISO/IEC 10118-3 [2] に記載されている SHA-1, SHA-224, SHA256, SHA-384, SHA-512 である.

6.2

鍵導出関数

鍵導出関数として 6.2.1 節で定義される MGF1 を推奨する. MGF1 は ISO/IEC 18033-2[1] における KDF1 と同じものである.

16

6.2.1

MGF1

MGF1 は 6.1 節で示されるハッシュ関数を利用したマスク生成関数である.
MGF1(M, n) は次のように定義される．
システムパラメータ:
入力:
出力:
エラー:
処理手順:

Hash
hashLenMnmask
INVALID

ハッシュ関数
ハッシュ関数の出力のオクテット長, 正の整数
マスクを生成するための乱数の種，オクテット列
出力のオクテット長, 正の整数
マスク, 長さ n のオクテット列

1. n0 を M のオクテット長とする. もし n0 + 4 が ハッシュ関数の入力ビット幅を越えていたならば , INVALID をエラー出力して処理を終了する.
lmn
2. cThreshold :=とする.
hashLen
3. もし cThreshold > 232 ならば , INVALID をエラー出力して処理を終了する.
4. M 0 を空オクテット列とする.
5. 整数 counter := 0 とする.
(a) counter を長さ 4 のオクテット列に変換する:
C := I2OSP(counter , 4).
(b) M と C を連結し , ハッシュ関数 Hash を作用させ，長さ hashLen のハッシュ値 H を生成する:
H := Hash(M k C).
(c) M 0 と H を連結し , その結果を再び M 0 とする:
M 0 := M 0 k H.
(d) counter := counter + 1 とする. もし counter < cThreshold ならば , 5 (a) に戻る.
6. オクテット列 M 0 の先頭 n オクテットを mask とする
0mask := M00 M10 · · · Mn−1.

7. mask を出力する.

参考文献[1] ISO/IEC 18033 – Information technology – Security techniques – Encryption algorithms –Part 2: Asymmetric ciphers, ISO, 2005a.
[2] ISO/IEC 10118 – Information technology – Security techniques – Hash functions – Part 3:
Dedicated Hash functions, ISO, 2004.

17

付録

A

パラメータ設定基準

PSEC-KEM パラメータの設定基準は以下の通りである.
pLen ≥ 20
hLen ≥ 16

B

パラメータ推奨値

PSEC-KEM パラメータの推奨値は以下の通りである.
pLen ≥ 32
KDF(256 ビット )= MGF1(SHA-256, hashLen = 32)

hLen = 32
R = Compressed
keyLen = 32

(256 ビット )

ある特定の楕円曲線パラメータについては脆弱性が指摘されているが , 適切な楕円曲線暗号のパラメータと実装については SECG のド キュメントを参照のこと . (http://www.secg.org/)

C

ASN.1 Syntax--###################################################################
ntt-ds OBJECT IDENTIFIER ::= {itu-t(0) networkoperator(3) ntt(4401) ds(5) }id-PSEC-KEM-v2
OBJECT IDENTIFIER ::={ ntt-ds 3 1 8 }DEFINITIONS EXPLICIT TAGS ::= BEGIN-- EXPORTS All; -IMPORTS
BlockAlgorithms
FROM EncryptionAlgorithms-3 { iso(1) standard(0)encryption-algorithms(18033) part(3)asn1-module(0) algorithm-object-identifiers(0) }HashFunctionAlgs, id-sha1, NullParms
FROM DedicatedHashFunctions { iso(1) standard(0)hash-functions(10118) part(3) asn1-module(1)dedicated-hash-functions(0) };--###################################################################-- oid definitions
18

OID ::= OBJECT IDENTIFIER -- alias-- Synonyms -is18033-2 OID ::= { iso(1) standard(0) is18033(18033) part2(2)}id-ac OID ::= { is18033-2 asymmetric-cipher(1) }id-kem OID ::= { is18033-2 key-encapsulation-mechanism(2) }id-dem OID ::= { is18033-2 data-encapsulation-mechanism(3) }id-sc OID ::= { is18033-2 symmetric-cipher(4) }id-kdf OID ::= { is18033-2 key-derivation-function(5) }id-rem OID ::= { is18033-2 rsa-encoding-method(6) }id-hem OID ::= { is18033-2 himer-encoding-method(7) }id-ft OID ::= { is18033-2 field-type(8) }-- Key encapsulation mechanisms -id-kem-psec OID ::= { id-kem psec(2) }-- Data encapsulation mechanisms -id-dem-dem1 OID ::= { id-dem dem1(1) }id-dem-dem2 OID ::= { id-dem dem2(2) }id-dem-dem3 OID ::= { id-dem dem3(3) }-- Symmetric ciphers -id-sc-sc1 OID ::= { id-sc sc1(1) }id-sc-sc2 OID ::= { id-sc sc2(2) }-- Key derivation functions -id-kdf-kdf1 OID ::= { id-kdf kdf1(1) }id-kdf-kdf2 OID ::= { id-kdf kdf2(2) }-- new field types oids-- id-ft-prime-field OID ::= { id-ft prime-field(1) }-- used only to define new basis typeid-ft-characteristic-two OID ::= { id-ft characteristic-two(2) }id-ft-odd-characteristic OID ::= { id-ft odd-characteristic(3) }id-ft-characteristic-two-basis OID ::={ id-ft-characteristic-two basisType(1) }charTwoPolynomialBasis OID ::={ id-ft-characteristic-two-basis
charTwoPolynomialBasis(1) }id-ft-odd-characteristic-basis OID ::= { id-ft-odd-characteristic
basisType(1)}oddCharPolynomialBasis OID ::= {id-ft-odd-characteristic-basis
oddCharPolynomialBasis(1)}-- MGF1 in PKCS #1 is equivalent to KDF1 here-- id-mgf1 should be used instead of id-kdf-kdf1 for compatibility-- with existing implementations
alg-mgf1-sha1 RsaesKeyDerivationFunction ::= {algorithm id-mgf1,
parameters HashFunction : alg-sha1

19

}
alg-sha1 HashFunction ::= {algorithm id-sha1,
parameters NullParms : NULL}
pkcs-1 OID ::= {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1}
id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8}
id-itu-sha1 OBJECT IDENTIFIER ::= { iso(1)identified-organization(3) oiw(14)secsig(3) algorithms(2) 26 }id-itu-sha224 OBJECT IDENTIFIER ::= {{ joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 4 }id-itu-sha256 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 1 }id-itu-sha384 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 2 }id-itu-sha512 OBJECT IDENTIFIER ::= { joint-iso-itu-t(2)country(16) us(840) organization(1) gov(101)csor(3) nistalgorithm(4) hashalgs(2) 3 }id-camellia128-cbc OBJECT IDENTIFIER ::=iso(1) member-body(2) 392 200011 61 security(1)algorithm(1) symmetric-encryption-algorithm(1) camellia128-cbc(2)id-aes OBJECT IDENTIFIER ::= { joint-iso-itu-t(2) country(16) us(840)organization(1) gov(101) csor(3)_ nistAlgorithms(4) 1 }id-aes128-CBC OBJECT IDENTIFIER ::= { id-aes 2 }--###################################################################-- KEM information objects
KeyEncapsulationMechanism ::= AlgorithmIdentifier {{ KEMAlgorithms }}KEMAlgorithms ALGORITHM ::= {{ OID id-kem-psec PARMS PsecKemParameters } |{ OID id-PSEC-KEM-v2 PARMS PsecKemParameters },... -- Expect additional algorithms -}--###################################################################-- PSEC-KEM-- an element of the group given in PsecKemParameters (may be 0)
PsecKemPrivateKey ::= INTEGER
PsecKemPublicKey ::= FieldElement

20

PsecKemParameters ::= SEQUENCE {group Group OPTIONAL,
keyDerivationFunction KeyDerivationFunction,
seedLength INTEGER (1..MAX),
keyLength KeyLength -- Length by byte}-- DEM specifications
DataEncapsulationMechanism ::= AlgorithmIdentifier {{DEMAlgorithms}}
DEMAlgorithms ALGORITHM ::= {{ OID id-dem-dem1 PARMS Dem1Parameters } |{ OID id-dem-dem2 PARMS Dem2Parameters } |{ OID id-dem-dem3 PARMS Dem3Parameters },... -- Expect additional algorithms -}Dem1Parameters ::= SEQUENCE{
symmetricCipher SymmetricCipher,mac MacAlgorithm}
Dem2Parameters ::= SEQUENCE{
symmetricCipher SymmetricCipher,mac MacAlgorithm,
labelLength INTEGER (0..MAX)}
Dem3Parameters ::= SEQUENCE{
mac MacAlgorithm,
msgLength INTEGER (0..MAX)}--###################################################################-- finite field, group, and elliptic curve representations
Group ::= CHOICE {groupOid OBJECT IDENTIFIER,
groupHashId OCTET STRING, -- defined in RFC2528
groupParameters GroupParameters}
GroupParameters ::= CHOICE {explicitFiniteFieldSubgroup[0] ExplicitFiniteFieldSubgroupParameters,
ellipticCurveSubgroup[1] EllipticCurveSubgroupParameters}
ExplicitFiniteFieldSubgroupParameters ::= SEQUENCE {fieldID FieldID {{FieldTypes}},
generator FieldElement,

21

subgroupOrder INTEGER,
subgroupIndex INTEGER}FIELD-ID ::= TYPE-IDENTIFIER
FieldID { FIELD-ID:IOSet } ::= SEQUENCE {fieldType FIELD-ID.&id({IOSet}),parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL}
FieldTypes FIELD-ID ::= {{ Prime-p IDENTIFIED BY prime-field } |{ Characteristic-two IDENTIFIED BY characteristic-two-field }|{ Odd-characteristic IDENTIFIED BY id-ft-odd-characteristic },... -- expect additional field types}-- prime fieds
Prime-p ::= INTEGER-- characteristic two fields
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER-- when basis is gnBasis then the basis shall be an optimal-- normal basis of Type T where T is determined as follows:-- if an ONB of Type 2 exists for the given value of m then-- T shall be 2, otherwise if an ONB of Type 1 exists for the-- given value of m then T shall be 1, otherwise T shall be-- the least value for which an ONB of Type T exists for the-- given value of m-- when basis is gnBasis then m shall not be divisible by 8-- note: the above rule is from ANSI X9.62-- note: for the given m and T the ONB is unique
Characteristic-two ::= SEQUENCE {m INTEGER,-- extension degreebasis CHARACTERISTIC-TWO.&id({BasisTypes}),parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})}
BasisTypes CHARACTERISTIC-TWO ::= {{ NULL IDENTIFIED BY gnBasis } |{ Trinomial IDENTIFIED BY tpBasis } |{ Pentanomial IDENTIFIED BY ppBasis } |{ CharTwoPolynomial IDENTIFIED BY charTwoPolynomialBasis },... -- expect additional basis types}
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {k1 INTEGER,

22

k2 INTEGER,
k3 INTEGER}-- characteric two general irreducible polynomial representation-- the irreducible polymial-- a(n)*x^n + a(n-1)*x^(n-1) + ... + a(1)*x + a(0)-- is encoded in the bit string with a(n) in the first bit, the-- following coefficients in the following bit positions and a(0)-- in the last bit of the bit string (one could omit a(n) and a(0)-- but it may be simpler and less error-prone to leave them in-- the encoding)-- the degree of the polynomial is to be inferred from the length-- of the bit string
CharTwoPolynomial ::= BIT STRING-- odd characteristic extension fields
ODD-CHARACTERISTIC ::= TYPE-IDENTIFIER
Odd-characteristic ::= SEQUENCE {characteristic INTEGER(3..MAX),
degree INTEGER(2..MAX),
basis ODD-CHARACTERISTIC.&id({OddCharBasisTypes}),parameters ODD-CHARACTERISTIC.&Type({OddCharBasisTypes}{@basis})}
OddCharBasisTypes ODD-CHARACTERISTIC ::= {{ OddCharPolynomial IDENTIFIED BY oddCharPolynomialBasis },... -- expect additional basis types}-- the monic irreducible polynomial is encoded as follows-- the leading coefficient is ignored-- the remaining coefficients define an element of the finite field-- which is encoded in an octet string using FE2OSP
OddCharPolynomial ::= FieldElement
EllipticCurveSubgroupParameters ::= SEQUENCE {version INTEGER { ecpVer1(1) } (ecpVer1),
fieldID FieldID {{ FieldTypes }},curve Curve,
generator ECPoint,-- Base point G
subgroupOrder INTEGER, -- Order mu of the base point
subgroupIndex INTEGER, -- The integer nu = #E(F)/mu...
}
Curve ::= SEQUENCE {aCoeff FieldElement,bCoeff FieldElement,23

seed BIT STRING OPTIONAL}--###################################################################-- auxiliary definitions
FieldElement ::= OCTET STRING -- obtained through FE2OSPECPoint ::= OCTET STRING -- obtained through EC2OSPKeyLength ::= INTEGER (1..MAX)
MacAlgorithm ::= AlgorithmIdentifier {{ MACAlgorithms }}MACAlgorithms ALGORITHM ::= {{ OID hMAC-SHA1 PARMS NULL } ,... -- Expect additional algorithms -}HashFunction ::= AlgorithmIdentifier {{ HashFunctionAlgorithms }}HashFunctionAlgorithms ALGORITHM ::= {HashFunctionAlgs | -- from 10118-3{ NULL IDENTIFIED BY id-itu-sha1 } |{ NULL IDENTIFIED BY id-itu-sha224 } |{ NULL IDENTIFIED BY id-itu-sha256 } |{ NULL IDENTIFIED BY id-itu-sha384 } |{ NULL IDENTIFIED BY id-itu-sha512 },... -- expect additional algorithms}
KeyDerivationFunction ::= AlgorithmIdentifier {{ KDFAlgorithms }}KDFAlgorithms ALGORITHM ::= {{ OID id-kdf-kdf1 PARMS HashFunction } |{ OID id-kdf-kdf2 PARMS HashFunction } |{ OID id-mgf1 PARMS HashFunction },... -- Expect additional algorithms -}SymmetricCipher ::= AlgorithmIdentifier {{ SymmetricAlgorithms }}SymmetricAlgorithms ALGORITHM ::= {{ OID id-sc-sc1 PARMS BlockCipher } |{ OID id-sc-sc2 PARMS BlockCipher } |{ OID id-camellia128-cbc PARMS BlockCipher } |{ OID id-aes128-CBC PARMS BlockCipher },... -- Expect additional algorithms -}BlockCipher ::= AlgorithmIdentifier {{ BlockAlgorithms }}--###################################################################-- external OIDs-- HMAC-SHA1
hMAC-SHA1 OID ::= {iso(1) identified-organization(3) dod(6) internet(1) security(5)24mechanisms(5) 8 1 2 }-- X9.62 finite field and basis types
ansi-X9-62 OID ::= { iso(1) member-body(2) us(840) 10045 }
id-fieldType OID ::= { ansi-X9-62 fieldType(1) }prime-field OID ::= { id-fieldType 1 }characteristic-two-field OID ::= { id-fieldType 2 }-- characteristic two basis
id-characteristic-two-basis OID ::= { characteristic-two-fieldbasisType(3) }gnBasis OID ::= { id-characteristic-two-basis 1 }tpBasis OID ::= { id-characteristic-two-basis 2 }ppBasis OID ::= { id-characteristic-two-basis 3 }--###################################################################-- Cryptographic algorithm identification -ALGORITHM ::= CLASS {&id OBJECT IDENTIFIER UNIQUE,&Type OPTIONAL}
WITH SYNTAX { OID &id [PARMS &Type] }AlgorithmIdentifier { ALGORITHM:IOSet } ::= SEQUENCE {algorithm ALGORITHM.&id( {IOSet} ),parameters ALGORITHM.&Type( {IOSet}{@algorithm} ) OPTIONAL}
END -- EncryptionAlgorithms-2 --25