なぜ暗号技術に有限体が重要なのか？
暗号技術は、多くの場合、数学的な概念に基づいています。具体的には、有限体や離散対数問題、楕円曲線などの概念が頻繁に利用されます。有限体は、楕円曲線暗号（ECC）などの暗号化技術で非常に重要な役割を果たします。ECCは、ビットコインをはじめとする多くのブロックチェーン技術で使用されています。
ECCは有限体上の楕円曲線の性質を利用しています。そのため、有限体とその操作を理解することは、ECCやブロックチェーン技術を理解する上で非常に重要です。また、有限体上の演算は、比較的小さな計算量で大きなセキュリティを確保することができるため、効率的な暗号化技術を構築するための鍵となります。
1. 有限体(Finite Fields)
有限体は代数的構造の一種であり、高度な数学に基づいています。具体的には、その要素数が有限であるフィールド（つまり、数の集合）です。要素数は必ず素数のべき乗となります。要素数がp（素数）のとき、その有限体はGF(p)と表現されます。
- 閉性：有限体の任意の2つの要素を演算（加算、減算、乗算、除算）しても、結果は有限体内に存在します。
- 加法と乗法の結合法則：a + (b + c) = (a + b) + c、a * (b * c) = (a * b) * c
- 加法と乗法の交換法則：a + b = b + a、a * b = b * a
- 加法と乗法の単位元の存在：すなわち、0と1が存在し、a + 0 = a、a * 1 = a
- 加法と乗法の逆元の存在：すなわち、各aに対し、-a（加法逆元）、1/a（乗法逆元）が存在します。
- 乗法に対する分配法則：a * (b + c) = a * b + a * c
これから実際に有限体を実装し、これらのすべての定義を検証していきます。今回は BigIntegerクラスを使って実装していきます。
BigIntegerクラスって何？
JavaのBigIntegerクラスは非常に便利な機能を提供しています。その中には、我々が有限体の操作を実装する際に必要なものが含まれています。
-
大きな整数の取り扱い：
BigIntegerクラスは、名前が示す通り、非常に大きな整数を扱うことが可能です。プリミティブ型のintやlongでは扱えない大きさの整数もBigIntegerならば問題なく扱うことができます。これは、暗号学などのフィールドでよく見られる非常に大きな数値を扱う際に非常に便利です。 -
モジュラー演算：
BigIntegerクラスは、モジュラー加算、モジュラー乗算、そしてモジュラー逆数の計算など、モジュラー演算に関する豊富なメソッドを提供しています。これは有限体の実装にとって重要な特徴であり、mod、modAdd、modMultiply、modInverseなどのメソッドが該当します。 -
Immutable（不変）：
BigIntegerは不変（Immutable）なクラスです。つまり、一度作成されたBigIntegerインスタンスはその後変更することができません。これは、多数のスレッドからアクセスされる可能性のあるデータや、誤って変更されることで致命的な結果を招く可能性のあるデータを扱う場合に便利です。また、オブジェクトが不変であると、それを安全に共有したり、再利用したりすることが容易になります。
2. Javaでの有限体の実装
Javaで有限体を表現するためのクラスを作成します。このクラスには、数値と素数をフィールドとして持ち、これらのフィールドの値によって有限体の要素を表現します。
ステップ1: FieldElementクラスの作成
まず、FieldElementクラスを作成します。このクラスは、有限体の要素を表すための基本的な演算を実装します。
import java.math.BigInteger;
public class FieldElement {
private BigInteger num;
private BigInteger prime;
// コンストラクタ、ゲッターメソッドなどを実装する
// ...
// 演算メソッド（加算、減算、乗算、除算）を実装する
// ...
}
ステップ2: コンストラクタの実装
FieldElementクラスのコンストラクタを実装します。コンストラクタは、与えられた数値が指定された範囲内にあるかどうかを検証します。
public FieldElement(BigInteger num, BigInteger prime) {
if (num.compareTo(prime) >= 0 || num.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("数字 " + num + " はフィールド範囲 0 から " + prime.subtract(BigInteger.ONE) + " の範囲外です");
}
this.num = num;
this.prime = prime;
}
ステップ3: 基本的な演算メソッドの実装
FieldElementクラスに基本的な演算メソッド（加算、減算、乗算、除算）を実装します。これらのメソッドは、与えられたフィールドの数値との演算を行い、結果を返します。
public FieldElement add(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を加算することはできません");
}
return new FieldElement(num.add(other.num).mod(prime), prime);
}
public FieldElement subtract(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を減算することはできません");
}
return new FieldElement(num.subtract(other.num).mod(prime), prime);
}
public FieldElement multiply(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を乗算することはできません");
}
return new FieldElement(num.multiply(other.num).mod(prime), prime);
}
public FieldElement divide(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を除算することはできません");
}
return new FieldElement(num.multiply(other.num.modInverse(prime)).mod(prime), prime);
}
完成コード
import java.math.BigInteger;
public class FieldElement {
private int num;
private int prime;
public FieldElement(int num, int prime) {
if (num >= prime || num < 0) {
throw new IllegalArgumentException("Num " + num + " not in field range 0 to " + (prime - 1));
}
this.num = num;
this.prime = prime;
}
public String toString() {
return "FieldElement_" + this.prime + "(" + this.num + ")";
}
public boolean equals(Object other) {
if (this == other) return true;
if (other == null || getClass() != other.getClass()) return false;
FieldElement that = (FieldElement) other;
return num == that.num && prime == that.prime;
}
}import java.math.BigInteger;
public class FieldElement {
private BigInteger num;
private BigInteger prime;
public FieldElement(BigInteger num, BigInteger prime) {
if (num.compareTo(prime) >= 0 || num.compareTo(BigInteger.ZERO) < 0) {
throw new IllegalArgumentException("数字 " + num + " はフィールド範囲 0 から " + prime.subtract(BigInteger.ONE) + " の範囲外です");
}
this.num = num;
this.prime = prime;
}
public BigInteger getNum() {
return num;
}
public BigInteger getPrime() {
return prime;
}
// numとprimeが等しい場合にtrueを返す
public boolean equals(FieldElement other) {
if (other == null) {
return false;
}
return num.equals(other.num) && prime.equals(other.prime);
}
// 加算処理
public FieldElement add(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を加算することはできません");
}
return new FieldElement(num.add(other.num).mod(prime), prime);
}
// 減算処理
public FieldElement subtract(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を減算することはできません");
}
return new FieldElement(num.subtract(other.num).mod(prime), prime);
}
// 乗算処理
public FieldElement multiply(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を乗算することはできません");
}
return new FieldElement(num.multiply(other.num).mod(prime), prime);
}
// 除算処理
public FieldElement divide(FieldElement other) {
if (!prime.equals(other.prime)) {
throw new IllegalArgumentException("異なるフィールドの2つの数値を除算することはできません");
}
return new FieldElement(num.multiply(other.num.modInverse(prime)).mod(prime), prime);
}
}
以下がテストコードです
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
FieldElement a = new FieldElement(new BigInteger("7"), new BigInteger("13"));
FieldElement b = new FieldElement(new BigInteger("6"), new BigInteger("13"));
FieldElement c = new FieldElement(new BigInteger("8"), new BigInteger("13"));
FieldElement zero = new FieldElement(BigInteger.ZERO, new BigInteger("13"));
FieldElement one = new FieldElement(BigInteger.ONE, new BigInteger("13"));
FieldElement negA = new FieldElement(a.getPrime().subtract(a.getNum()), a.getPrime());
FieldElement invA = new FieldElement(a.getNum().modInverse(a.getPrime()), a.getPrime());
// 閉性のテスト
System.out.println(a.add(b) instanceof FieldElement); // trueを出力するはずです
System.out.println(a.subtract(b) instanceof FieldElement); // trueを出力するはずです
System.out.println(a.multiply(b) instanceof FieldElement); // trueを出力するはずです
System.out.println(a.divide(b) instanceof FieldElement); // trueを出力するはずです
// 結合法則のテスト
System.out.println(a.add(b.add(c)).equals(a.add(b).add(c))); // trueを出力するはずです
System.out.println(a.multiply(b.multiply(c)).equals(a.multiply(b).multiply(c))); // trueを出力するはずです
// 交換法則のテスト
System.out.println(a.add(b).equals(b.add(a))); // trueを出力するはずです
System.out.println(a.multiply(b).equals(b.multiply(a))); // trueを出力するはずです
// 単位元の存在のテスト
System.out.println(a.add(zero).equals(a)); // trueを出力するはずです
System.out.println(a.multiply(one).equals(a)); // trueを出力するはずです
// 逆元の存在のテスト
System.out.println(a.add(negA).equals(zero)); // trueを出力するはずです
System.out.println(a.multiply(invA).equals(one)); // trueを出力するはずです
// 乗法に対する分配法則のテスト
System.out.println(a.multiply(b.add(c)).equals(a.multiply(b).add(a.multiply(c)))); // trueを出力するはずです
}
}
2.2. 練習問題 1
FieldElementクラスを使用して、以下の有限体を作成してみてください：
- GF(7)の中の要素2を表現してみてください。
- GF(13)の中の要素6と要素7を作成し、それらが等しいか確認してみてください。
解答
public class Main {
public static void main(String[] args) {
FieldElement a = new FieldElement(2, 7);
System.out.println(a); // print: FieldElement_7(2)
FieldElement b = new FieldElement(6, 13);
FieldElement c = new FieldElement(7, 13);
System.out.println(b.equals(c)); // print: false
}
}
このJavaのコードを使えば、Pythonのコードと同じように有限体の要素を作成し、表示し、比較することができます。ただし、Javaでは演算子のオーバーロードができないため、例えば足し算や掛け算などの操作
を自然な形で行うことはできません。そのため、それらの操作については、別途メソッドを作成して実装する必要があります。
3. モジュロ演算(Modulo Arithmetic)
有限体内の加算と減算は、通常の加算と減算に似ていますが、結果は有限体の要素数（すなわち、prime）でモジュロしたものとなります。
3.2. 練習問題 2
上記のaddメソッドとsubtractメソッドを使用して、以下の演算を行ってみてください：
- GF(7)の中で、4 + 6を計算してみてください。
- GF(13)の中で、6 - 7を計算してみてください。
解答
public class Main {
public static void main(String[] args) {
FieldElement a = new FieldElement(4, 7);
FieldElement b = new FieldElement(6, 7);
System.out.println(a.add(b)); // print: FieldElement_7(3)
FieldElement c = new FieldElement(6, 13);
FieldElement d = new FieldElement(7, 13);
System.out.println(c.subtract(d)); // print: FieldElement_13(12)
}
}
Pythonでの実装
以下のPythonコードは、上記のJavaコードと同じ機能を持つFieldElementクラスを定義しています。
以下は__add__を定義したものです。これは、自身のクラスのインスタンス（self）と別のインスタンス（other）との間で加算を行うための特殊メソッドです。
def __add__(self, other):
if self.prime != other.prime:
raise TypeError('異なるフィールドの2つの数字を加算することはできません')
num = (self.num + other.num) % self.prime
return self.__class__(num, self.prime)
まず、if self.prime != other.prime: の部分で、自分自身の prime プロパティと他のオブジェクトの prime プロパティが等しいかどうかを確認します。等しくない場合は、TypeError を送出します。これは、異なる有限体（Finite Field）間での加算は意味をなさないためです。
次に、num = (self.num + other.num) % self.prime の部分で、自身の num プロパティと他のオブジェクトの num プロパティを足し合わせて、その結果を自身の prime プロパティで割った余りを計算します。これは、有限体における加算の定義（モジュロ計算）を表現しています。
最後に、return self.__class__(num, self.prime) で新たにクラスのインスタンスを生成し、そのインスタンスを返します。ここで、self.__class__ は現在のインスタンスと同じクラスを指します。これは、有限体における加算結果も同じ有限体に属するべきであるため、新たなインスタンスを生成して返す必要があります。
self.__class__(num, self.prime) という表現について詳しく説明します。この表現は、「現在のインスタンスと同じクラスの新しいインスタンスを生成する」という意味を持ちます。ここで、self.__class__ は現在のインスタンスと同じクラスを指し、その後ろのカッコ内は新しいインスタンスを生成する際に必要な引数を指します。つまり、この表現全体は「現在のインスタンスと同じクラスの新しいインスタンスを、num と self.prime を引数にして生成する」という意味になります。
class FieldElement:
def __init__(self, num, prime):
# numがprime以上または0未満の場合、エラーメッセージを表示します
if num >= prime or num < 0:
error = f'数字{num}はフィールド範囲0から{prime -1}の範囲外です'
raise ValueError(error)
self.num = num
self.prime = prime
def __repr__(self):
return 'FieldElement_{}({})'.format(self.prime, self.num)
def __eq__(self, other):
# otherがNoneの場合、Falseを返します
if other is None:
return False
# 2つのFieldElementオブジェクトが等しい場合、Trueを返します
return self.num == other.num and self.prime == other.prime
def __ne__(self, other):
# これは==演算子の逆です
return not (self == other)
def __add__(self, other):
# 2つのフィールドが異なる場合、エラーメッセージを表示します
if self.prime != other.prime:
raise TypeError('異なるフィールドの2つの数字を加算することはできません')
num = (self.num + other.num) % self.prime
return self.__class__(num, self.prime)
def __sub__(self, other):
# 2つのフィールドが異なる場合、エラーメッセージを表示します
if self.prime != other.prime:
raise TypeError('異なるフィールドの2つの数字を減算することはできません')
num = (self.num - other.num) % self.prime
return self.__class__(num, self.prime)
def __mul__(self, other):
# 2つのフィールドが異なる場合、エラーメッセージを表示します
if self.prime != other.prime:
raise TypeError('異なるフィールドの2つの数字を乗算することはできません')
num = (self.num * other.num) % self.prime
return self.__class__(num, self.prime)
def __pow__(self, exponent):
num = pow(self.num, exponent, self.prime)
return self.__class__(num, self.prime)
def __truediv__(self, other):
# 2つのフィールドが異なる場合、エラーメッセージを表示します
if self.prime != other.prime:
raise TypeError('異なるフィールドの2つの数字を除算することはできません')
# フェルマーの小定理を利用して除算を実行します
num = (self.num * pow(other.num, self.prime - 2, self.prime)) % self.prime
return self.__class__(num, self.prime)
以下がテストコードです
# aをFieldElement(7, 13)、bをFieldElement(6, 13)、cをFieldElement(8, 13)として定義します
a = FieldElement(7, 13)
b = FieldElement(6, 13)
c = FieldElement(8, 13)
# 閉性のテスト
print(isinstance(a + b, FieldElement)) # Trueを出力するはずです
print(isinstance(a - b, FieldElement)) # Trueを出力するはずです
print(isinstance(a * b, FieldElement)) # Trueを出力するはずです
print(isinstance(a / b, FieldElement)) # Trueを出力するはずです
# 加法と乗法の結合法則のテスト
print(a + (b + c) == (a + b) + c) # Trueを出力するはずです
print(a * (b * c) == (a * b) * c) # Trueを出力するはずです
# 加法と乗法の交換法則のテスト
print(a + b == b + a) # Trueを出力するはずです
print(a * b == b * a) # Trueを出力するはずです
# 加法と乗法の単位元の存在のテスト
zero = FieldElement(0, 13)
one = FieldElement(1, 13)
print(a + zero == a) # Trueを出力するはずです
print(a * one == a) # Trueを出力するはずです
# 加法と乗法の逆元の存在のテスト
neg_a = FieldElement(-a.num % a.prime, 13) # aの加法逆元
inv_a = FieldElement(pow(a.num, a.prime - 2, a.prime), 13) # aの乗法逆元
print(a + neg_a == zero) # Trueを出力するはずです
print(a * inv_a == one) # Trueを出力するはずです
# 乗法に対する分配法則のテスト
print(a * (b + c) == a * b + a * c) # Trueを出力するはずです
これらのメソッドを使って、有限体内での加算と減算を自然な形で表現できます。次に、乗算と除算、そして累乗についても同様にメソッドを定義します。それは次の記事に書きたいと思います。