繰り返し二乗法を用いて、 を で割った余り （）を求めよ。すなわち
を満たす整数 を求めよ。
暗号理論
扱うテーマ: RSA 暗号の鍵生成・暗号化・復号、ディフィー・ヘルマン鍵共有・エルガマル暗号、離散対数・位数と原始根、楕円曲線上の点の加算とスカラー倍、古典暗号（アフィン暗号・ヴィジュネル暗号）、ハッシュの衝突確率（誕生日問題）
難易度の目安（大学数学）
- 難易度 1 教科書の例題レベル
- 難易度 2 教科書の演習問題レベル
- 難易度 3 期末試験の応用レベル
- 難易度 4 大学院入試の標準レベル
- 難易度 5 大学院入試の難問・数学コンテストレベル
繰り返し二乗法を用いて、 を で割った余り （）を求めよ。
繰り返し二乗法を用いて、 を で割った余りを求めよ。すなわち、 を満たす整数 を求めよ。
であるから、 は法 で逆元をもつ。拡張ユークリッドの互除法を用いて、 を満たす整数 （すなわち ）を求めよ。
合同式
を満たす整数 のうち、 であるものを求めよ。すなわち、 を求めよ。であるから、 は法 で逆元をもつ。
を満たす整数 （すなわち ）を、拡張ユークリッドの互除法を用いて求めよ。英字 文字を と数に対応させる。長さ の鍵語の文字を表す数を （それぞれ 以上 以下の整数）とし、平文の 文字目（）を表す数 を
で定まる の文字に置き換えるヴィジュネル暗号を考える。平文 をこの方法で暗号化したところ、暗号文は になった。組 を求めよ。
英字 文字を と数に対応させる。長さ の鍵語を数の列 （各 は の整数）で表す。平文の 文字目（）に対応する数を とし、暗号文の 文字目に対応する数 を
で定める（ヴィジュネル暗号）。ある平文をこの方法で暗号化したところ、暗号文は であった。また、平文の最初の 文字は であることがわかっている。鍵 を求めよ。
英字 文字を と数に対応させる。長さ の鍵 （各 は の整数）を使うヴィジュネル暗号では、平文の 文字目（）に対応する数 を
を満たす に変えて暗号文を作る。ある平文の最初の 文字は であり、それを暗号化した暗号文の最初の 文字は であった。鍵 を数の組で求めよ。
出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は互いに異なる 個の入力 を用意し、それぞれのハッシュ値 を計算する（ は正の整数）。この 個のハッシュ値の中に等しいものが少なくとも 組ある（衝突が起こる）確率が を超えるような のうち、最小のものを求めよ。
出力が 通りの値のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
互いに異なる 個の入力 のハッシュ値のうち、少なくとも つが一致する（衝突が起こる）確率 を、近似式
で見積もる。この近似値が 以上となる最小の正の整数 を求めよ。ただし、 として計算してよい（ は自然対数）。出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
互いに異なる 個の入力（ は正の整数）のハッシュ値を計算したとき、少なくとも 組の衝突（同じハッシュ値をもつ つの入力）が起こる確率を とする。 を近似式
で見積もる。この近似値が 以上となる最小の正の整数 を求めよ。ただし、 として計算してよい（ は自然対数）。英字 文字を と数に対応させ、各文字 を
で暗号化する。この暗号の復号関数を
の形で表すとき、整数 （）の組 を求めよ。英字 文字を と数に対応させます。整数 （、）を鍵とするアフィン暗号
で、1 文字ずつ暗号化します。暗号文の文字は、 を 以上 以下の整数で表したものです。この暗号で、平文の文字 は に、平文の文字 は に暗号化されました。鍵 を求めてください。
英字 文字を と数に対応させる。鍵を とするアフィン暗号
で暗号化された文字 （）を元に戻す復号関数を
の形で表すとき、整数の組 を求めよ。受信者は素数 , を選び、 とした。暗号化指数を とし、公開鍵 を公開した。復号指数 は
を満たす整数である。送信者は平文 （ を満たす整数）を （）で暗号化し、暗号文 を送った。受信者が で復号して得る平文 を求めよ。受信者は素数 , を選び、 と暗号化指数 を公開鍵として公開した。秘密鍵の復号指数 は
を満たす整数とする。送信者は平文 （ を満たす整数）を （）により暗号化し、暗号文 を送った。受信者が により復号して得る平文 を求めよ。素数 と、法 の原始根 を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。アリスは秘密の整数 を選んで を、ボブは秘密の整数 を選んで を計算し、互いに送る（）。このとき、2 人が共有する鍵 （）を求めよ。
素数 と、法 の原始根 を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。アリスは秘密の整数 を、ボブは秘密の整数 を選ぶ。
アリスは 、ボブは を計算して互いに送り、それぞれ共有鍵 を求める。ただし はいずれも 以上 以下の整数とする。
の値を、組 の形でこの順に求めよ。
素数 と、法 の原始根 を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。
アリスは秘密の整数 を選び、（）をボブに送る。ボブは秘密の整数 を選び、（）をアリスに送る。
このとき、2 人が共有する鍵 （）を求めよ。
素数 に対し、 は法 での原始根であり、 における の位数は である。ベビーステップ・ジャイアントステップ法を用いて、
を満たす整数 を求めよ。ただし とする。素数 を法として、 の位数は です（ は法 の原始根）。ベビーステップ・ジャイアントステップ法を用いて、
を満たす整数 を求めてください。とし、 とする。 は法 の原始根であり、 の法 での位数は である。
を満たす整数 を、ベビーステップ・ジャイアントステップ法を用いて求めよ。ただし とする。
素数 について、 は法 の原始根である（ の法 での位数は ）。ポーリッヒ・ヘルマン法を用いて、
を満たす整数 を求めよ。素数 について、 は法 の原始根である（ の法 での位数は ）。
を満たす整数 を、 を利用するポーリッヒ・ヘルマン法で求めよ。素数 について、 は法 の原始根です（ の法 での位数は ）。ポーリッヒ・ヘルマン法を用いて、 を満たす整数 を求めよ。
有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。 上の 2 点 、 について、 とする。ただし は 以上 以下の整数で表す。組 を求めよ。有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。上の 2 点 , について、和 の座標 を求めよ。ただし、 は 以上 以下の整数で表すこと。
有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。上の 2 点 , について、 とする。座標 を求めよ。ただし、 は 以上 以下の整数で答えよ。
素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の秘密鍵は であり、公開鍵 を公開している。送信者は平文 （ の整数）を、ある整数 を用いて
と暗号化し、暗号文 を受信者に送った。受信者が秘密鍵 を用いて復号して得る平文 を求めよ。素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の秘密鍵は で、公開鍵は である。送信者は平文 （ の整数）を、ある整数 を用いて
と暗号化し、暗号文 を送った。受信者が秘密鍵を用いて復号したときの平文 を求めよ。素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の秘密鍵は である。受信者は、ある平文 （ の整数）を暗号化した暗号文
を受け取った。ただし、送信者は秘密の整数 を選び、, （ は受信者の公開鍵）として暗号文を作ったものとする。復号の式 を用いて、平文 を求めよ。有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。 上の点 について、点 の座標 を求めよ。ただし、座標は 以上 以下の整数で表し、 の順に答えること。有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。 上の点 について、 を順に計算して の位数を求め、それを使って の座標 を求めよ。ただし、座標は 以上 以下の整数で答えよ。有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。点 は 上の点である。 の位数を求めたうえで、スカラー倍 を求めよ。答えは座標の組 で書き、 は 以上 以下の整数で表せ。
素数 , を用いて RSA 暗号の鍵を作る。 とし、公開鍵の暗号化指数を とする。秘密鍵の復号指数 は、 を満たす の整数とする。
平文 （ を満たす整数）を , により暗号化したところ、暗号文 が得られた。平文 を求めよ。
有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）によって群をなす。点 は 上の点である。 の座標 を求めよ。ただし は の整数で表し、答えは の組で答えよ。
受信者は素数 , を選び、 と暗号化指数 を公開鍵として公開した。送信者は平文 （ を満たす整数）を
によって暗号化し、暗号文 を受信者に送った。受信者は秘密鍵の復号指数 を , を満たす整数として求め、 により復号する。平文 を求めよ。
素数 と、法 の原始根 を公開パラメータとして、アリスとボブがディフィー・ヘルマン鍵共有を行う。
アリスは秘密の整数 を選び、（）をボブに送る。ボブは秘密の整数 を選び、（）をアリスに送る。その後、アリスは を、ボブは を計算し、これを共有鍵 （）とする。
共有鍵 を求めよ。
を奇素数とする。 と互いに素な整数 の を法とする位数とは、 をみたす最小の正の整数 のことであり、位数が である整数を を法とする原始根という。 を を法とする原始根とする。
ディフィー・ヘルマン鍵共有では、秘密の 0 以上の整数 に対して を で割った余りが公開される。このとき、すべての 0 以上の整数 に対して
が成り立つこと（したがって公開された値から秘密 の偶奇がわかること）を証明せよ。ただし、次の事実は用いてよい。
- と互いに素な整数 の位数を とすると、0 以上の整数 について となるのは のとき、かつそのときに限る
- 素数 が整数の積 を割り切るならば、 または である出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなす。つまり、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は、署名してもらいたい「正当な文書」の変種 と、すり替えたい「不正な文書」の変種 を用意する。これら 個の入力は互いに異なる。攻撃者は
を満たす が少なくとも 組存在するとき、攻撃に成功するものとする。正当な文書どうし、または不正な文書どうしでハッシュ値が一致しても、それだけでは成功とはみなさない。攻撃に成功する確率を、既約分数で求めよ。
英字 文字を と数に対応させる。整数の組 を鍵とするアフィン暗号
で 1 文字ずつ暗号化する。ただし は を満たす整数で、 とする。このような鍵 のうち、暗号化を 2 回続けて行うと必ず元の文字に戻る、すなわち を満たすすべての整数 について
が成り立つ鍵（暗号化と復号が同じ写像になる鍵）は何個あるか。ただし が恒等写像になる鍵 も数に含める。RSA 暗号の公開鍵として、相異なる 2 つの素数 の積 と暗号化指数 が公開されている。暗号化は、平文 （ を満たす整数）に対して
で行う。いま、攻撃者はオイラー関数の値 を知ったとする。暗号化しても値が変わらない平文、すなわち
を満たす整数 の個数を求めよ。素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は である（秘密鍵 は を満たす。 は公開されていない）。
平文 （ の整数）を暗号化するとき、送信者は整数 を選び、
として暗号文 を送る。ある送信者が、本来は毎回選び直すべき を使い回して、2 つの平文 を同じ で暗号化した。得られた暗号文は
である。攻撃者は何らかの方法で であることを知った。秘密鍵 を求めずに、平文 （ の整数）を求めよ。有限体 上の楕円曲線
を考えます。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群になります。この曲線と基点 を公開パラメータとして、アリスとボブが楕円曲線ディフィー・ヘルマン鍵共有を行います。アリスは秘密鍵 を選んで公開鍵 を送り、ボブは秘密鍵 を選んで公開鍵 を送ります。二人が共有する点を とします。
の座標 を、 の整数の組で求めてください。
合成数 を法とする離散対数を考える。
を満たす最小の正の整数 を求めよ。出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなす。すなわち、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は互いに異なる 個の入力 についてハッシュ値 を計算する。このとき、ある値 について となる が 個以上存在する確率を求めよ。この事象を「 重衝突（3-マルチコリジョン）が起こる」という。
RSA 暗号の受信者は、相異なる素数 を選んで とし、公開鍵 を公開した。秘密鍵の復号指数 は
を満たす整数である。ここで である。送信者は平文 （ を満たす整数）を （）によって暗号化して送る。いま攻撃者は、 そのものは知らないが、 であることを知った。さらに暗号文 を傍受した。この暗号文に対応する平文 を求めよ。
素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は である。秘密鍵 は を満たすが、公開されていない。
送信者は平文 （ を満たす整数）を暗号化するとき、一時鍵 を選び、
として暗号文 を送る。ある送信者が、本来は毎回取り替えるべき一時鍵 を、2 つの平文 , の暗号化に同じ値のまま使ってしまった。その結果、送られた暗号文は次の 2 つである。
攻撃者は、1 つ目の暗号文の平文が であることを知っている。このとき、2 つ目の暗号文の平文 （）を求めよ。素数 と法 の原始根 を用いるエルガマル暗号を考える。受信者の秘密鍵を 、公開鍵を とする。平文 （ の整数）は、送信者が整数 （）を選び
として暗号文 に暗号化される。送信者は、誤って同じ を使い回して 2 つの平文 を暗号化し、暗号文 と をこの順に送った。盗聴者は つ目の平文が であることを知っている。 つ目の平文 を求めよ。
素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者は秘密鍵 を選び、公開鍵 （）を公開している。
送信者は平文 （ の整数）を、整数 を選んで
により暗号文 に変換して送る。受信者が受け取った暗号文が であるとき、平文 を求めよ。素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は である（秘密鍵 は を満たすが、公開されていない）。
平文 （ の整数）を暗号化するとき、送信者は乱数 （ の整数）を選び、
として暗号文 を送る。ある送信者が、2 つの平文 を暗号化する際に、誤って同じ乱数 を使ってしまい、暗号文はそれぞれ
となった。攻撃者は、1 つ目の平文が であることを知っている。このとき、2 つ目の平文 を求めよ。素数 と、法 の原始根 を公開パラメータとするエルガマル暗号を考える。受信者の公開鍵は である（秘密鍵 は を満たすが、公開されていない）。
平文 （ の整数）を暗号化するとき、送信者は乱数 を選び、
として暗号文 を送る。ある送信者が、2 つの平文 , を暗号化する際に、誤って同じ乱数 を使ってしまった。その結果、暗号文はそれぞれ
となった。攻撃者は何らかの方法で であることを知った。このとき、秘密鍵 や乱数 を求めずに得られる （ の整数）を求めよ。素数 について、 は法 の原始根である（ の法 での位数は ）ことを用いてよい。
を満たす整数 のうち、法 における位数（ となる最小の正の整数 ）がちょうど であるものをすべて考える。それらの の総和を求めよ。
出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は互いに異なる入力 をこの順に つずつ に問い合わせ、それまでに得た出力のどれかと同じ出力が初めて得られた時点で問い合わせをやめる。すなわち、
を とし、攻撃者は 回問い合わせる。 の期待値 を求めよ。素数 について、 は法 の原始根である（ の法 での位数は ）。
合同式
を満たす整数 はただ つ存在する。その を求めよ。英字 文字を と数に対応させ、鍵 のアフィン暗号
で 1 文字ずつ暗号化する。ここで鍵は整数の組 で、、、 を満たすものとする。鍵 が次の 2 つの条件をともに満たすとき、「よい鍵」と呼ぶ。
- 条件 : 暗号化を 2 回続けて行うと元に戻る。すなわち、 を満たすすべての整数 について が成り立つ（暗号化と復号が同じ操作になる）。
- 条件 : どの文字もそれ自身には暗号化されない。すなわち、 を満たすどの整数 についても である。
よい鍵 の個数を求めよ。
を奇素数、 を を法とする原始根とする。 と互いに素な整数 について、 をみたす整数 が存在するとき を を法とする平方剰余、存在しないとき平方非剰余という。
アリスとボブが群 上でディフィー・ヘルマン鍵共有を行う。アリスは秘密の正の整数 、ボブは秘密の正の整数 を選び、、 を公開し、共有鍵を とする。
このとき、「 が を法とする平方非剰余であるための必要十分条件は、 と がともに を法とする平方非剰余であることである」を証明せよ。ただし、原始根の定義（ の位数が であり、 と互いに素な任意の整数は を法としてある （）と合同になること）と、「 となる整数 は の倍数に限る」ことは用いてよい。
を素数とし、 を を法とする剰余類全体とする。整数 は かつ をみたすとし、アフィン暗号の暗号化写像 を
で定める。正の整数 に対して、 を 回合成した写像を と書く。正の整数 について、「すべての に対して が成り立つ（すなわち、同じ鍵で 回暗号化すると必ず平文に戻る）」ための必要十分条件は であること（とくにこの条件は によらないこと）を証明せよ。
ただし、 が素数で ならば、 をみたす整数 は に限ることは用いてよい。
を相異なる奇素数とし、、 とおく。正の整数 は をみたすとする（RSA 暗号の公開鍵 と秘密鍵 ）。中国剰余定理を使った高速な復号（CRT-RSA）のために、次を定める。
- を を で割った余り、 を を で割った余りとする（、）。
- 整数 を、 をみたす整数のうちの 1 つとする（ は相異なる素数なので、このような は存在する）。をみたす整数 （暗号文）に対して、
- を を で割った余り、 を を で割った余り（、）、
- を を で割った余り（）、
-とおく。ここで は と互いに素であるとは限らない（ や、 が または の倍数である場合も含む）。また、整数 に対して と定める（ のときも含む）。このとき、 かつ であることを証明せよ。
ただし、フェルマーの小定理と、「整数 が相異なる素数 のそれぞれで割り切れるならば で割り切れる」ことは用いてよい。
英字 文字を と数に対応させ、 の元とみなす。正の整数 と鍵 に対し、鍵の長さ のヴィジュネル暗号は、平文 を
で暗号文 に変換する（ は を で割った余り）。鍵の成分はどれも から の任意の値をとってよいものとする。いま、長さ の文字列全体の集合 上で、まず鍵の長さ の鍵 でヴィジュネル暗号化し、その結果をさらに鍵の長さ の鍵 でヴィジュネル暗号化する二重暗号化を考える。鍵の組 は全部で 通りある。
鍵の組 をすべて動かしたとき、この二重暗号化によって得られる から への写像は何通りあるか。答えは の累乗の形で答えよ。
素数 について、 は法 の原始根である（ の法 での位数は ）。
を満たす整数 （ の底 に関する離散対数）を求めよ。英字 文字を と数に対応させ、アフィン暗号
で 1 文字ずつ暗号化する。ここで鍵 は , を満たす整数で、 は と互いに素である（暗号化は 1 対 1 である）。ある暗号文について、平文の文字 が に、平文の文字 が に暗号化されていることがわかった。この暗号の復号関数を
の形に表すとき、整数の組 を求めよ。出力が 通りしかない簡易ハッシュ関数 を考える。 はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は互いに異なる入力 を順に選んで を 回ずつ計算し、すでに計算した出力のどれかと同じ出力が初めて得られた時点で計算をやめる（衝突の発見）。このとき計算した の値の個数を とする（たとえば ならば ）。
確率変数 の期待値 を求めよ。
有限体 上の楕円曲線
を考える。 の 有理点全体に無限遠点 を単位元として通常の加法（弦と接線による加法）を入れた群において、点 をとる。点 の座標 を求めよ。ただし は , を満たす整数で表し、 の組で答えよ。
ディフィー・ヘルマン鍵共有の公開パラメータとして、素数 と、法 の原始根 を選びたい。ここで整数 が法 の原始根であるとは、 の法 における位数（ を満たす最小の正の整数 ）が であることをいう。
を満たす法 の原始根 のうち、最小のものを求めよ。
出力が 通りの値 のどれかになるハッシュ関数 を考える。 はランダムオラクルとみなし、互いに異なる入力に対する出力は、それぞれ独立に 通りの値から等確率で選ばれるものとする。
攻撃者は互いに異なる入力 を順に選び、ハッシュ値 を 1 つずつ計算していく。そして、計算したハッシュ値がそれまでに得たハッシュ値のどれかと一致した時点（衝突が初めて見つかった時点）で計算をやめる。
やめるまでに計算したハッシュ値の個数を とする（たとえば ならば ）。 の期待値 を求めよ。
有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。点 について、 となる最小の正の整数 （ の位数）を求めよ。英字 文字を と数に対応させ、鍵 のアフィン暗号
で 1 文字ずつ暗号化する。鍵は、 かつ を満たす整数 と、 を満たす整数 の組 とする（全部で 通り）。ある鍵 について、同じ鍵で 3 回続けて暗号化すると、どの文字ももとの文字に戻る、すなわち
が成り立つとする。このような鍵 の個数を求めよ（恒等写像になる鍵 も数える）。有限体 上の楕円曲線
を考える。 の 有理点全体は、無限遠点 を単位元とし、通常の加法（弦と接線による加法）で群をなす。上の 点
について、 を満たす最小の正の整数 を求めよ。ただし は を 個加えた点を表す。を標数が でも でもない体とし、 は をみたすとする。 とおき、楕円曲線
の 有理点全体に無限遠点 を加えた集合 を、通常の加法（ が単位元）で群と考える。 のとき は重根をもたないこと、および次の事実は用いてよい。
- 点 に対し である。 座標が等しい 2 つのアフィン点 は または をみたす。
- のとき、 はアフィン点であり、 とおくと、 の 座標は である。 のときは である。さらに
とおく。 のアフィン点 について、「 の位数が であるための必要十分条件は である」ことを証明せよ。
条件に合う問題はありません。