2026年10月06日 第2回
計算量的安全性はすぐに理解できたが、 情報理論的安全性は本当に存在できるのか最初疑問に思ったが、 証明を見て理解できた。
理解できたのであれば良かったです．
前回も少し触れられていましたが、
授業の最初の旧日本陸軍の暗号の話で、
暗号の理論自体が完璧だとしても人間が暗号化すると油断したりすることは割とあり得る話だと思ったため、
そういう意味でも暗号化や復号をコンピュータが行なう現代の通信方式は画期的だなと考えました。
また、
今までもユークリッドの互除法というもの自体は知っていたのですが証明は見たことがありませんでした。
今回の講義で証明を学び、
どのような理由で最大公約数が求められるのかが分かりました。
やはり一番弱いのは人間ということですね．
分かったこと
ワンタイムパッドが安全と言える理由:平文 M と暗号文 C について P(M=m | C=c) = P(M=m) が成り立つ,つまり暗号文を見ても平文についての情報が増えないことが「安全」の定義だと分かりました.鍵 K をランダムに選ぶため,M と C の4通りの組(0,0),(0,1),(1,0),(1,1)がどれも P(M=m)/2 になる,という場合分けの計算も追えました.
分からなかったこと
条件付き確率の式の意味づけ:P(M=m | C=c) = P(M=m) を示す計算で,「P(M=0 かつ C=0) = P(M=0 かつ K=0)」と置き換えられる理由(C = M⊕K なので K が決まれば対応する C が決まる)を,その場ではすぐに飲み込めませんでした.
でも理解できたということ？
今回の講義では、 整数の約数と倍数の基本的な考え方や、 その表し方について理解することができた。 特に、 整数 a,b に対して a=bq となる整数 q が存在するとき、 a はb の倍数であり、 bはaの約数であるという関係を、 b|a と表せることが分かった。 また、 ある整数 a_1、 a_2 がともにbの倍数であれば、 それらに整数を掛けて足し合わせた c_1a_1+c_2a_2 もbの倍数になるという、 整数の線形結合についても学んだ。 証明では、 a_1=q_1b、 a_2=q_2bと置くことで、 共通する b をくくり出せることが理解できた。 一方で、 「線形結合」という言葉自体にはまだ慣れておらず、 なぜこの考え方が今後の最大公約数などの学習で重要になるのかについては十分に理解できなかった。 今後は具体的な数字を使った例題を解きながら、 線形結合の意味や使い方を理解していきたい。
そうですね．演習をやって貰えば良いかもしれません．
今日取り上げられていた定義、 ユークリッドの互除法は高校で触れたはもののそれっきりといったものだったので改めて復習できて良かった。 ただ、 高校の時から思っていたのですが、 ユークリッドの互除法は何回も何回も割り算と余りを求めるステップを繰り返さねばならず、 元の数が大きくなるにつれその計算量も膨大になってしまうのが難点かなと思いました。 計算量を減らす裏ワザのようなものはないのか気になりました。
裏技というかどうか不明ですが，調べてみて教えてください．
One Time Padのようにとても安全な暗号方式であっても、 鍵の配送問題があったり再利用できないなどの欠点があるので、 暗号方法はそれぞれの安全な度合いと欠点を把握してどの方法を使用するかを考える必要があるのだと改めて思った。 また、 VernamさんやFrenkMillerさんのように様々な職種の人が暗号方式を見つけ出していることを知り、 今も昔も第三者に内容が知られないように連絡を取り合うことはどの業界でも重要なことだったのだと改めて感じた。
そうですね．確かにどの業界でも大切ですね．
整数の線型結合の定理でnこの整数a_i(i=1,2,...,n)がある整数bの倍数であるとき、
a_i(i=1,2,...,n)の線形結合
c_1*a_1 + c_2*a_2 + ・・・ + c_n*a_n=∑c_i*a_i もbの倍数 となるところが直感的に違いそうでもaがbの倍数であるので最終的にbの共通因数で全てくくれてbの倍数となるところが理解できた。
その通りです．理解していますね．
今回の講義では、 約数や倍数、 最大公約数・最小公倍数について学びました。 ユークリッドの互除法を使うことで大きな数でも割り算の余りを繰り返して最大公約数を求められることが分かりました。 今までは素因数分解を使って求めることが多かったので、 別の求め方があることが印象に残りました。 最大公約数と最小公倍数の関係については少し複雑だったので演習問題を解きながら理解を深めたいです。
不明なところは質問してください．
また，講義後にタイポ (というかなぜか変数が消えていた) を指摘してもらいました．
次回，改めて資料を配布します．
今回はこれから使う数学的知識の復習であったが、 商についての証明やユークリッド互除法についての証明は新たな知識として学べた。
そうでしたか．それは良かった．
最大公約数や最小公倍数など混同してしまうことがあったが定義や定理を再確認することができた。 また、 ユークリッドの互除法についての計算は知っていたが細かな内容や定理までは知らなかったので理解を深めることができた。
それはよろしいと思います．
今回の講義を受講して、 暗号には単に文字を別の文字に置き換えるだけではなく、 数学的な考え方が多く使われていることが分かった。 特に、 One-Time Padでは鍵を一度しか使わないことで高い安全性を実現できることや、 暗号の安全性を考える上で乱数が重要であることが印象に残った。 また、 最大公約数を求めるユークリッドの互除法など、 暗号とは直接関係なさそうな数学の計算が暗号技術につながっていることも分かった。 一方で、 確率や数式を使って暗号の安全性を説明する部分は少し難しく、 なぜその計算で安全性を証明できるのかまでは十分に理解できなかった。 今後は、 今回出てきた数学的な考え方と暗号の関係をもう少し詳しく理解したい。
そうですか．情報理論的安全性は一番の肝って感じなのですけどね．
旧日本陸軍の無限乱数式暗号の話が非常に興味深かったです。
しかし、
コード変換表はあらかじめ共有することが可能だと思うのですが、
乱数はどのように共有するのでしょうか。
あらかじめ乱数表を送ったとして、
どこかに乱数の指定を記載するのでしょうか。
2章のお話はユークリッド互除法含め高校の既習範囲でしたが、
丁寧に記法から説明してくださり分かりやすかったです。
いい質問ですね．次回触れますが， 乱数表というのをあらかじめ作っておいたようです．
情報理論的に安全とは暗号文cを観測したあとで平文がmである確率が観測する前に平文がmである確率と等しいことだと分かりました。
ワンタイムパッドを1ビットで調べると平文が0である確率をrとしても鍵が0と1を等確率で取るため暗号文が0になる確率も1になる確率も2分の1になります。
平文と暗号文の組を四通りとも確かめるとどれも平文の確率の2分の1になり、
定義の式が成り立つことが分かりました。
nビットでは平文と同じ長さの鍵が要ります。
鍵は一度使ったら捨てて作り直す必要があり、
鍵配送問題がそのまま残るため使い勝手が悪いことも分かりました。
そうなのですよ．使い勝手が悪いのです．．．
バーナム暗号が情報理論的安全性が保障されている証明と、
公約数、
公倍数などの基礎、
そしてユークリッドの互除法のやり方がわかった。
暗号を破られた歴史を考えたら機械の性能の向上などだけではなく、
人間の面倒くさがりとかの方が暗号を破るきっかけになるのかなと思った。
その通りです．一番弱いのは人間なのです．．．．
今回の授業では最小公倍数、 最大公約数の出し方、 ユークリッドの互除法をやりましたが、 a,b,q,rに数字を置いて最大公約数を出す際、 アルゴリズムなど丁寧に教えてくださり、 理解ができました。 また、 今日学んだことが鍵問題などにどう関係しているのか理解を深めたいです。
理解してくれたのであれば良かったと思います． 今日，次回，その次などは，公開鍵暗号方式のための基本ですね．
今回の講義で、 ワンタイムパッドが情報理論的に安全であるとは、 暗号文 c を観測した後に平文が m である確率 P(M=m|C=c) が、 観測する前の確率 P(M=m) と等しいことだと分かりました。 1ビットの場合に、 鍵を等確率で選べば平文の出方に偏りがあってもこの等式が成り立つことを、 場合分けで確かめられた点が印象に残りました。 一方で、 鍵の共有が必要なこと、 鍵を使い捨てること、 平文と同じ長さの鍵が要ることから、 使い勝手がよくないことも理解しました。 後半では、 商と余りの定理の証明が存在性と一意性の二段階で進むことや、 a=bq+r のとき gcd(a,b)=gcd(b,r) が成り立ち、 これを繰り返すのがユークリッドの互除法であることが分かりました。 長方形を正方形のタイルで埋め尽くす図の説明で、 この関係を直感的に理解できました。
素晴らしい．完璧ですね．
旧日本陸軍でもone time padの案があったということですが、 その暗号はどのようにして鍵である乱数を共有しようとしていたのでしょうか?共通鍵である以上鍵配送問題を解決する必要もあるため、 それもその暗号が採用されなかった理由になるのでしょうか?
良い質問ですね．次回触れますが，乱数表のようなものを作って， 使ったページを捨てる良いにしていたと思います．
今回の講義では、 中学校や高校でこれまで使ってきた倍数や約数、 最大公約数、 最小公倍数などについて、 改めて定義を確認し、 その性質や定理を数学的に証明していくことで、 これまでよりも深く理解することができました。 今までは、 計算方法や公式を覚えて使っていることが多かったため、 なぜその性質が成り立つのかを考えることができて良かったです。 一方で、 約数の定義について少し疑問に思いました。 定義2.1の内容からすると、 負の数も約数として考えられると思います。 しかし、 講義では6の約数として1、 2、 3、 6が挙げられており、 この科目では約数については正の約数のみを考えるのでしょうか。
その通り，負の数も入りますが，
この例では正のものにしましたが，
講義でそのようにいいませんでしたかね．
今回の講義では倍数と約数の記号を用いた表し方や最小公倍数lcm、 最大公約数gcdを新たに学んだ。 また互いに素な数の性質やユークリッドの互除法のアルゴリズムを改めて学んだ。 例を用いてユークリッドの互除法の計算をしたことで手計算で求める場合とプログラムとして実装する場合のどちらにおいても最大公約数を求めるという点でユークリッドの互除法はどれだけ優れているものなのか体感できた。
理解してくれましたね．素晴らしいですね．
今回は、 倍数・約数の話で、 すでに知っていることが多かった。 それでも、 何となくで覚えているだけで、 あいまいな部分があったため、 そういったものを明確にできたのは良かった。 また、 ユークリッドの互除法に関して、 何度か教わっているが、 毎回自信をもって覚えられていなかったため、 今回また復習することができて良かった。
復習できたのは良かったと思います．
ユークリッドの互除法は、 高校で習ったときから計算方法だけを機械的に覚えていましたが、 今回の授業を通して、 なぜその方法で最大公約数を求めることができるのかという原理がなんとなく理解できた気がしました。 また、 線形代数学で学んだ内容と倍数の考え方がつながっていることも分かり、 別々に学んでいた数学の内容が結びついているのが面白いと感じました。
繋がるのはとても大切ですね．
公倍数や公約数の性質、 ユークリッドの互除法について改めて学習することができた。 また、 最小公倍数と最大公約数の関係を表す定理については初めて知ったが、 証明を通して理解を深めることができた。
理解できましたか．良かった．
今回の授業では,ユークリッド互除法を使って最大公約数を求める方法を学んだ。
余りを利用して同じ計算を繰り返すことで,効率よく求められることが分かった。
特に,数が大きくなっても同じ手順で計算できる点が印象に残った。
普段の数学とは少し違い,計算の手順そのものを効率化するという考え方が情報系らしく感じた。
そうですね．確かに情報系らしいかも．
互除法は分かっていて、 なんで成り立つのか分からなかったが、 今回の講義でなんで成り立つのか分かった。
わかったのであれば良かったです．
今回の授業を通して、 ユークリッドの互除法や最大公約数、 最小公倍数などの証明や法則などを学んだ。 自分もこれらの法則は忘れているものが多かったので、 いい復習になった。 ここからもう一度復習をして、 しっかりと定着させていこと思う。
そうですね．ぜひそうしてください．
今回の授業では、
最大公約数や最小公倍数、
ユークリッドの互除法について学んだ。
ユークリッドの互除法は以前に授業でも扱ったことがあったため、
計算方法自体はある程度知っていたが、
今回は最大公約数や最小公倍数の性質と関連づけて学ぶことで、
改めて理解を深めることができた。
また、
RSA暗号で公開鍵を選ぶ際にも、
互いに素であることを確認するためにユークリッドの互除法が使われていたことを思い出し、
今回学んだ内容が情報系の分野でも繋がっていると思った。
疑問に思ったのは、
ユークリッドの互除法を3つ以上の整数に対して使う場合、
最初の2つの最大公約数を求めてから、
3つ目の数との最大公約数を求める方法でよいのか気になった。
ユークリッドの互除法は基本的に二つの数が対象だと思います．
三つ目の入れるとしたら，まず最初の二数の最大公約数を求めて，
その後，その求めた最大公約数と三つ目の数の最大公約数を求めるのではないですかね．
lcmが最小公倍数を表してgcdが最大公約数を表すことがわかった。 ユークリッドの互除法の復習ができた。
理解できて良かった．
ユークリッドの互除法で最大公約数を計算するやり方や、 商と余りの関係自体は高校の復習としてスムーズに理解できた。 ワンタイムパッドの解読不能性も、 1ビットの排他的論理和を使って条件付き確率の式を導く流れは納得できた。 ただ、 文字式が入ってきたときの互除法の証明や、 nビットに拡張したときの確率の扱いにはまだ少し引っかかる部分があった。 もし鍵が完全にランダムじゃなかったらどれくらい解読されやすくなるのかも気になった。
おー，いいコメントですね．
暗号理論などでは定量的に議論されている話ですね．