1 mod 97 とは 35x ≡ 1

構造の数理レポート問題
提出場所：講義あるいは試験のとき
担当：桔梗宏孝
提出期限：2014 年 7 月 30 日 (水)
この用紙に記入して，3 ページを綴じて提出すること。可能なら両面印刷で 2 枚にしてください。
学籍番号
氏名
問 1. 以下の空欄に 0∼9 の数字を埋めて，正しい議論になるよ
(iii) 2 つの素数 41 と 101 を利用した RSA 暗号の鍵を作る。
うに完成せよ。ただし，右肩に同じ記号 (カタカナ) のある枠に
公開鍵を 17 とする。41 × 101 = 4141 なので，0 ≤ x < 4141
は同じ数字を入れること。
に対し，y = x17 mod 4141 が x の暗号である。この暗号の復
(i) 35−1 mod 97 をユークリッドの互除法を使って求める。
号のための秘密鍵を求める。
41 − 1 = 40 と 101 − 1 = 100 の最小公倍数は 200 なので，
35−1 mod 97 とは 35x ≡ 1 (mod 97) かつ 1 ≤ x < 97 となる
e = 17−1 mod 200 を求めればよい。これは，次のように求
整数 x のことである。
まる。
次の式において右端は理由である。たとえば，(1) − (2) × 2 は，
(2) の両辺の 2 倍をそれぞれ (1) の対応する辺から引いて得ら
れる合同式であることを表わしている。
(1)
97
≡
0 · 35 (mod97)
(2)
35
≡
1 · 35 (mod97)
(3)
27
≡
−2 · 35 (mod97)
(4)
8
≡
3 · 35 (mod97)
≡ −
(5)
· 35 (mod97)
(6)
2
≡
25 · 35 (mod97)
(7)
1
≡ −
· 35 (mod97)
≡
· 35 (mod97)
(1) − (2) × 2
1=
ア
イ
ア
イ
· 35 −
200 ≡
0 · 17 (mod200)
(2)
17 ≡
1 · 17 (mod200)
(3)
13 ≡
−11 · 17 (mod200)
(4)
4 ≡
· 17 (mod200)
(2) − (3)
(5)
1 ≡
· 17 (mod200)
(3) − (4) ×
(2) − (3)
−
≡
· 17 (mod200)
(3) − (4) ×
得られた秘密鍵 e に対し，y ≡ x (mod 4141) を示せばこの方
(4) − (5) × 2
法で復号できることがわかる。
(5) − (6)
フェルマーの小定理より，素数 p に対し x ̸≡ 0 (mod p) なら
ば xp−1 ≡ 1 (mod p) なので，
である。すると，x ̸≡ 0 (mod 101) のとき
· 97
y e = x17e
=x
ウ
(ii) x を整数とする。
{
x ≡ a (mod 4)
= (x
≡1
x ≡ b (mod 25)
b (mod 100)
エ
·x
· x (mod 101)
y e = x17e ≡ 0 ≡ x (mod 101)
である。これは次の議論からわかる。上の式を変形して，
なので，いつでも
25x ≡ 25a (mod 100) · · · (1)
4x ≡ 4b (mod 100)
y e ≡ x (mod 101)
· · · (2)
である。同様に y e ≡ x (mod 41) も示せる。
を考えると上の式を得る。また，逆は明
y e − x は 101 でも 41 でも割り切れるので，
らかである。



 x ≡ 1 (mod 4)
x ≡ 12 (mod 25)


 0 ≤ x < 100
を解くと，x =
ウ
である。x ≡ 0 (mod 101) のときも
a−
とし，(1) − (2) ×
エ
)
≡ x (mod 101)
の必要十分条件は，
{
≡ 1 (mod 101)
x ̸≡ 0 (mod 101) ならば x
,
である。
x≡
(1) − (2) × 11
e
よって，
35−1 mod 97 =
(1)
y e − x ≡ 0 (mod 4141)
である。
である。
1
学籍番号
事実 1．
氏名
誤り箇所が 2 つ以内で，
C ≡ (Ay + 1)S(y) (mod y 4 ) (A, C ∈ F8 )
2
3
4
5
6
問 2. 以下の空欄を 0, 1, 2, 3, 4, 5, 6, α, α , α , α , α , α の
が成り立つとき，
いずれかで埋め，正しい議論になるように完成せよ。ただし，
E(y) = ea y a (誤り箇所は 1 つ)，
右肩に同じ記号 (カタカナ) のある枠には同じものを入れるこ
C = ea αa ，A = αa と書ける。
と。また，指示があるものは指示に従うこと。
さて，上の Reed-Solomon 符号を受信したところ，
f1 = (α, α, α6 , α, 0, 0, α5 )
8 元体
F8 = F2 [x]/(1011) = {0, 1, 10, 11, 100, 101, 110, 111}
であった。シンドローム多項式の係数を計算すると
f1 (α) = α · α6 + α · α5 + α6 · α4 + α · α3 + α5
を考える。1011 は x3 + x + 1 のこと (係数ベクトル) である。
F8 の要素は係数ベクトルで表現された 2 次以下の F2 係数
= 1 + α6 + α3 + α4 + α5
多項式である。和 + は F2 係数多項式としての和 (桁ごとの
= 1 + 101 + 11 + 110 + 111
,
=
mod 2 の和) で，積 · は F2 係数多項式としてかけた後に 1011
2
2
で割った余りをとる演算とする。α = 10 とすると，α のべきは
f1 (α ) = α ,
次の表で表される。下の段が上の式の値である。
f1 (α3 ) = 1,
α2
α
α3
α4
α5
α6
f1 (α4 ) = α5
α7
となる。ユークリッドの互除法により，鍵方程式の解を求める。
10 100
11 110 111 101 1
たとえば，α3 = 1000 ≡ 1000 − 1011 ≡ 11 (mod 1011) のよ
(1) y 4 ≡ 0 · S(y) (mod y 4 )
うに計算できる。
(2) α5 y 3 + y 2 + α2 y +
原始元 α = 10 を利用した F8 上の誤り訂正能力 2 の Reed-
(3)
≡(
カ
y+
Reed-Solomon 符号 f に対し誤り E が加わって，f1 になった
α4 ≡ (α5 y + 1)S(y) (mod y 4 )
とする。
シンドローム多項式 S(y) は次の通りである。
4
3
3
2
事実 1 より，誤り多項式は E(y) = ea y a と書け，a =
2
S(y) = f1 (α )y + f1 (α )y + f1 (α )y + f1 (α)
また，事実 1 より，α4 = ea αa なので，ea =
f =(
Ω(y) ≡ Λ(y)S(y) (mod y 4 )
,
,
,
と推測される。
deg Ω(y) < deg Λ(y) ≤ 2
Ω(y) と Λ(y) は互いに素
この鍵方程式の解は定数倍を除いて一意的である。
さて，E(y) の y a の係数が ea ̸= 0 だったとする。
Sa (y) = ea αa (1 + αa y + α2a y 2 + α3a y 3 )
とおいて両辺を αa y 倍すると
αa ySa (y) = ea αa (αa y + α2a y 2 + α3a y 3 + α4a y 4 )
両辺をそれぞれ引くと
オ
)
となるので
ea αa ≡ (1 − αa y)Sa (y) (mod y 4 ).
に当てはまる式を次の中から選び，○で囲め。
α y
α4a y 4
y3
である。し
たがって，もとの符号 f は
Ω(y)，Λ(y) を求めればよい。
(1 − αa y)Sa (y) = ea αa (1 −
で
ある。
= E(α4 )y 3 + E(α3 )y 2 + E(α2 )y + E(α).
誤り位置が 2 箇所以内の誤り訂正には，次の鍵方程式の解
3a 3
) · S(y) (mod y 4 )
(3) は (1) − (2) × 多項式で得られる。
)−1
(
カ
を (3) の両辺にかけると
Solomon 符号を考える。
オ
≡ 1 · S(y) (mod y 4 )
y4
(i) 誤り箇所が 1 つの場合，E(y) = ea y a ，S(y) = Sa (y) と書
けるので，鍵方程式の解は定数倍を除いて
ea αa ≡ (1 + αa y)S(y) (mod y 4 )
だけである。(F8 では −1 = 1 であることも使っている。)
(問 2 は次ページに続く。)
2
,
,
,
)
学籍番号
氏名
問 2 の続き
(ii) 誤り箇所が 2 つの場合，E(y) = ea y a + eb y b ，
S(y) = Sa (y) + Sb (y) と書ける。
ea αa ≡ (1 + αa y)Sa (y) (mod y 4 ),
eb αb ≡ (1 + αb y)Sb (y) (mod y 4 )
より，
ea αa (αb y + 1) + eb αb (αa y + 1)
≡ (αa y + 1)(αb y + 1)S(y) (mod y 4 )
鍵方程式の解は定数倍を除いてこれだけである。
事実 2．
誤り箇所が 2 つ以内で，
Cy + D ≡ (Ay 2 + By + 1)S(y) (mod y 4 )
A, B, C, D ∈ F8 ，Cy + D と Ay 2 + By + 1 は互いに素
が成り立つとき，
E(y) = ea y a + eb y b (誤り箇所は 2 つ)，
Cy + D = ea αa (αb y + 1) + eb αb (αa y + 1),
Ay 2 + By + 1 = (αa y + 1)(αb y + 1)
と書ける。
再び Reed-Solomon 符号を受信したところ，
f1 = (α, 1, α6 , 0, 0, 0, α5 )
であった。シンドローム多項式の係数を計算すると
f1 (α) = α，f1 (α2 ) = 0，f1 (α3 ) = α2 ，f1 (α4 ) = α4 である。
ユークリッドの互除法により，鍵方程式の解を求める。
(1) y 4 ≡ 0 · S(y) (mod y 4 )
(2) α4 y 3 + α2 y 2 + α ≡ 1 · S(y) (mod y 4 )
y2 +
(3)
y+
≡(
) · S(y) (mod y 4 )
y+
((3) は (1) − (2) × 多項式による)
(4)
(
≡(
y+
キ
y2 +
y+
キ
) · S(y) (mod y 4 )
((4) は (2) − (3) × 多項式による)
)−1
を (4) の両辺にかけると
α3 y + α ≡ (αy 2 + α2 y + 1)S(y) (mod y 4 )
を得る。y = α2 とすると，αy 2 + α2 y + 1 = 0 である。
よって，
αy 2 + α2 y + 1 = (
y + 1)(
a
y + 1)
b
事実 2 より，E(y) = ea y + eb y ，a =
3
a
b
b
，b =
，
a
α y + α = ea α (α y + 1) + eb α (α y + 1)
と書ける。よって，
E(y) =
である。(E(y) を具体的な式で書け。)
以上
3

Download Report