秘密分散法(Shamir の (k,n) しきい値法)に関する下記の問題を解いて回答を提出しなさい。
素数p = 31のとき、秘密情報s(0≤s <p)を以下の多項式f(x)を用いて分散するものとする。
f(x) = s + ax + bx2 + cx3(modp)
ここで、a,b,cは乱数 (0≤a,b,c <p)である。
xの各値(0 < x < p)に対応する分散情報y=f(x)の値を下の表に示す。
x
1
2
3
4 5
6
7
8
9 10 11 12 13 14 15
y
10
26
27 19
8
0
1
17
23 25 29
20
10
35
20 30
x
16
17
18
19
20 21
y
10 28 28 16 29 11
230
22
23
24
30 17 28
22
25 26 27 28 29 30
7 22 17 29
22
2
(1) 異なるxの値を4つ選び、秘密情報sの値を求めなさい (乱数a,b,c の値を求める必要は
ない)。 ただし、xの値は、各自の学籍番号 (最後のチェックディジット1桁は除く)の
下3桁をmとするとき、 x1 = (mmod30) + 1 (つまり、mを30で割った余りに1を加え
る)、 x2 = (m+7mod30) + 1, x3 = (m + 11 mod30) +1、 x4 = (m + 17mod30) +1と
選びなさい。
(2) 上記(1)とは異なるxの組み合わせについて、 同様に秘密情報s の値を求め、 (1)の結果と
等しくなることを確認しなさい。
(1),(2)共に導出方法の説明や途中の式を適宜示すこと(答えだけ書いてあるものは不可)。
回答は、pdf 形式にてアップロードしなさい。