JPH02305039A - 認証方式 - Google Patents
認証方式Info
- Publication number
- JPH02305039A JPH02305039A JP1125224A JP12522489A JPH02305039A JP H02305039 A JPH02305039 A JP H02305039A JP 1125224 A JP1125224 A JP 1125224A JP 12522489 A JP12522489 A JP 12522489A JP H02305039 A JPH02305039 A JP H02305039A
- Authority
- JP
- Japan
- Prior art keywords
- prover
- data
- confirmer
- random number
- authentication
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
〔産業上の利用分野〕
この発明は相手認証（例えば電話の話し相手が 一
本当に自分の話したい相手であることを認証する）。
本当に自分の話したい相手であることを認証する）。
本人認証（例えば自分が本当にその本人であること全相
手や他人に認証してもらう）、データ認証（データが正
しいことを認証してもらう）などの認証システムにおけ
る認証方式に関するものである。− 〔従来の技術〕 認証方式では、現在効率良く計算するアルゴリズムが知
られていない、と言う意味での計算困難な問題に安全性
の根拠を置く方式が用いられる。
手や他人に認証してもらう）、データ認証（データが正
しいことを認証してもらう）などの認証システムにおけ
る認証方式に関するものである。− 〔従来の技術〕 認証方式では、現在効率良く計算するアルゴリズムが知
られていない、と言う意味での計算困難な問題に安全性
の根拠を置く方式が用いられる。
そうした計算困難な問題の１つに平方剰余問題がある。
ｍを与えられた正整数とするとき、Ｘがｍと互いに素、
すなわち（ｘ、ｍ）＝１．かつヤコビ記号Ｃ，／ｍ）
が１である正整数Ｘに対してと定義する。ｍの素因数
分解が分かつている場合は＋ Ｑ”を効率良く計算する
アルゴリズムは知られている。しかしｍの素因数分解が
知られていない場合、今日まで効率良く計算するアルゴ
リズムは知られていない。したがって、もしＱｍを効率
良く計算するアルゴリズムを開発した者、あるいはｍの
素因数分解を知っている者が、 Ｑｍ を計算する能力
を持つと言うことを通信相手となる確認者に納得させる
場合、これを達成する信頼性の高い安全な通信システム
を構成する必要がある。ここで言う信頼性の高い安全な
通信システムとして満たすべき条件として １、確認者はＱｒｎを計算する能力を持つ者は認証する
。
すなわち（ｘ、ｍ）＝１．かつヤコビ記号Ｃ，／ｍ）
が１である正整数Ｘに対してと定義する。ｍの素因数
分解が分かつている場合は＋ Ｑ”を効率良く計算する
アルゴリズムは知られている。しかしｍの素因数分解が
知られていない場合、今日まで効率良く計算するアルゴ
リズムは知られていない。したがって、もしＱｍを効率
良く計算するアルゴリズムを開発した者、あるいはｍの
素因数分解を知っている者が、 Ｑｍ を計算する能力
を持つと言うことを通信相手となる確認者に納得させる
場合、これを達成する信頼性の高い安全な通信システム
を構成する必要がある。ここで言う信頼性の高い安全な
通信システムとして満たすべき条件として １、確認者はＱｒｎを計算する能力を持つ者は認証する
。
２、確認者はＱｍを計算する能力を持たない者は認証し
ない。
ない。
３、証明者は、確認者にＱｍを計算する能力を持つとい
う事だけを伝え、それ以外の情報は漏らさない。
う事だけを伝え、それ以外の情報は漏らさない。
０３つがあげられる。
こうしたＱｍを効率よく計算する者を認証する信頼性の
高い安全な通信システムとして従来しられるシステムは
ＧＭＲ（Ｇｏｌｄｗａ９ｓｅｒ−Ｍｉｃａｌｉ−Ｒａｃ
ｋｏｆ ｆ ）の方法（Ｓ、 Ｇｏｌｄｗａｓｓｅｒ、
Ｓ、 Ｍｉｃａｌｉ。
高い安全な通信システムとして従来しられるシステムは
ＧＭＲ（Ｇｏｌｄｗａ９ｓｅｒ−Ｍｉｃａｌｉ−Ｒａｃ
ｋｏｆ ｆ ）の方法（Ｓ、 Ｇｏｌｄｗａｓｓｅｒ、
Ｓ、 Ｍｉｃａｌｉ。
ａｎｄ Ｃ，Ｒａｃｋｏｆｆ、気Ｔｈｅ ｋｎｏｗｌｅ
ｄｇｅ ＣｏｍｐＩｅｘ−ｉｔｙ ｏｆ ＩｎＬｓｒａ
ｃｔｉｖｅ Ｐｒｏｏｆ Ｓｙｇｔｓｍｓ ’ 。
ｄｇｅ ＣｏｍｐＩｅｘ−ｉｔｙ ｏｆ ＩｎＬｓｒａ
ｃｔｉｖｅ Ｐｒｏｏｆ Ｓｙｇｔｓｍｓ ’ 。
Ｐｒｏｃｅｅｄｉｎｇｓ ｏｎ ｔｈｅ １７ ｔｈ
Ａｎｎｕａｌ ＡＣＭＳｙｍｐｏｓｉｕｍ ｏｎ Ｔｈ
ｅ−ｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ 。
Ａｎｎｕａｌ ＡＣＭＳｙｍｐｏｓｉｕｍ ｏｎ Ｔｈ
ｅ−ｏｒｙ ｏｆ Ｃｏｍｐｕｔｉｎｇ 。
１９８５．２９１−３０４） を用いた認証システム
がある。第２図はその認証システムのブロック図で。
がある。第２図はその認証システムのブロック図で。
（１）は証明者の操作により乱数を生成する乱数発生器
、（２）は証明者の操作により、乱数発生器より生成さ
れる乱数や演算装置よシ出力される演算結果や、確認者
より送られるデータを記憶するメモリ。
、（２）は証明者の操作により、乱数発生器より生成さ
れる乱数や演算装置よシ出力される演算結果や、確認者
より送られるデータを記憶するメモリ。
（３）は証明者の操作により演算を行う演算装置、（４
）は証明者の操作によりＱｍの計算を行い、与えられた
数が平方剰余であるか否かの判定を行う判定装置、（５
）は証明者と確認者が用いる通信回線、（６）は確認者
の操作により、乱数発生器より生成される乱数や演算装
置より出力される演算結果や、確認者より送られるデー
タを記憶するメモ！ｊ 、 ＋７１は確認者の操作に上
り演算を行う演算装置、（８）は確認者の操作により乱
数を生成する乱数発生器である。
）は証明者の操作によりＱｍの計算を行い、与えられた
数が平方剰余であるか否かの判定を行う判定装置、（５
）は証明者と確認者が用いる通信回線、（６）は確認者
の操作により、乱数発生器より生成される乱数や演算装
置より出力される演算結果や、確認者より送られるデー
タを記憶するメモ！ｊ 、 ＋７１は確認者の操作に上
り演算を行う演算装置、（８）は確認者の操作により乱
数を生成する乱数発生器である。
次に動作について説明する。
ステップ１：証明者は乱数発生器（１）を用いて正整数
の乱数ａを生成しメモリ（２）に保存する。
の乱数ａを生成しメモリ（２）に保存する。
ステップ２：証明者はメモリ（２）より乱数ａを呼び出
し、乱数ａがｍと互いに素であるか否か、すなわち （ａ、ｍ）＝１ を満たすか否か、演算装置（３）を用いて判定する。
し、乱数ａがｍと互いに素であるか否か、すなわち （ａ、ｍ）＝１ を満たすか否か、演算装置（３）を用いて判定する。
（” ＋ ｍ ） ” １であればステップ３へ＋（”
ｉ’）≠１であればステップ１へ戻る。
ｉ’）≠１であればステップ１へ戻る。
ステップ３：証明者はメモリ（２）より前記乱数ａを呼
び出し、前記乱数ａの法ｍのもとてのヤコビ記号が１で
あるか否かすなわち （ａ ／ ｍ ） ＝ １ 釜満たすか否か、演算装＠（３）を用いて判定する。
び出し、前記乱数ａの法ｍのもとてのヤコビ記号が１で
あるか否かすなわち （ａ ／ ｍ ） ＝ １ 釜満たすか否か、演算装＠（３）を用いて判定する。
（’ａ ／ ｍ ） ＝’ｌであればステップ４へ、（
ａ／ｍ）＝−１であればステップ１へ戻る。
ａ／ｍ）＝−１であればステップ１へ戻る。
ステジブ４：証明者は前記乱数ａをメモＵ ｔ２＋より
呼び出し、乱数ａが平方非剰余であるか否か、すなわち
。
呼び出し、乱数ａが平方非剰余であるか否か、すなわち
。
Ｑｍ’（ａ） ＝ ０
を満たすか否か１判定装置（４）を用いて判定すゐ。
Ｑｍ （ａ’）＝ Ｏであればステップ５ ヘ、 Ｑｍ
（ａ） ＝ １ であればステップ１へ戻る。
（ａ） ＝ １ であればステップ１へ戻る。
ステップ５：証明者は前記乱数ａｔ通信回線（５）を通
して１通信相手となる確認者に送る。
して１通信相手となる確認者に送る。
ステップ６：確認者は証明者より送られる乱数ａをメモ
１月Ｇ）に保存し、乱数ａのヤコビ記号が１であるか、
すなわち （ａ／ｍ’）立１ を満たすか否か、演算装置（７）を用いて確かめる。
１月Ｇ）に保存し、乱数ａのヤコビ記号が１であるか、
すなわち （ａ／ｍ’）立１ を満たすか否か、演算装置（７）を用いて確かめる。
（ａ ／ ｍ ） ＝ １であればステップ１へ、さも
なくば正当な証明者でないとして操作を打ち切る。
なくば正当な証明者でないとして操作を打ち切る。
以下のステップＴ〜ステップ２１ ｆ ｎ ＝ ｌｏｇ
２ｍ回縁り返す。
２ｍ回縁り返す。
ステップ７：確認者は乱数発生器（８）を用いてランダ
ムにｒＱεｃ ｔｔ ｍ−１１Ｃｘε（０，１）を選ぶ
。
ムにｒＱεｃ ｔｔ ｍ−１１Ｃｘε（０，１）を選ぶ
。
ステップＢ：確認者は演算装置を用いてＣ工＝０ならば
ｘ ＝： ｒ Ｏ２，ＣＸ ” １ならばｚ＝ａｒ（１
２を計算する。
ｘ ＝： ｒ Ｏ２，ＣＸ ” １ならばｚ＝ａｒ（１
２を計算する。
ステップ９：確認者は前記演算結果Ｘを通信回線（５）
を通して、証、間者に送る。
を通して、証、間者に送る。
ステップ１０：確認者は乱数発生器（８）を用いて２つ
のランダムな集合（ただし大きさはｎ＝ｌｏｇ２ｍのサ
イズ） Ｔ＝（ｔｌ、 ｔ２．−・、ｔｎ： Ｊ＝ｒ１ｍｏｄｍ
）。
のランダムな集合（ただし大きさはｎ＝ｌｏｇ２ｍのサ
イズ） Ｔ＝（ｔｌ、 ｔ２．−・、ｔｎ： Ｊ＝ｒ１ｍｏｄｍ
）。
３＝ （ｋｎ＋１ 、ｔｎ＋２．・”、 ｔ２ｎ：
ｔｉ＝ ａｒ１２ ｎｏｄ ｍ ）（ｔｊＥ
［：１． ｍ−１］ ｊ＝１．−． ２ｎ）を選ぶ。
ｔｉ＝ ａｒ１２ ｎｏｄ ｍ ）（ｔｊＥ
［：１． ｍ−１］ ｊ＝１．−． ２ｎ）を選ぶ。
ステップ１１：確認者は乱数発生器（８）を用いてＴ″
′Ｓの元をランダムな順序で通信回線（５）を通して、
証明者に送る。
′Ｓの元をランダムな順序で通信回線（５）を通して、
証明者に送る。
ステップ１２：証明者は乱数発生器（１）を用いて大＠
サＩｄ、 ｎ （Ｄ 、 Ｔ”” Ｓ ’ＤＨ分集合
Ｚ （ＣＴ”Ｓ ） ヲランダムに選ぶ。
サＩｄ、 ｎ （Ｄ 、 Ｔ”” Ｓ ’ＤＨ分集合
Ｚ （ＣＴ”Ｓ ） ヲランダムに選ぶ。
ステップ１３：証明者は前記２を通信回線（５）を通し
て、確認者に送る。
て、確認者に送る。
ステップ１４：確認者は２の各元２θ２に対し。
ｚ ＝ ｒ２ｍｏｄ ｍ あるいはｚ ＝ ａｒ２ｍ
ａｄ ｍを満たすｒを演算装置（７）を用いて計算する
。もしもＴ−ＺとＳ−Ｚの大きさがｄだけ違う場合、確
認者ＢはＴ−ＺとＳ−Ｚの大きい方の集合から、乱数発
生器を用いてランダムにｄ個の集合ｔ１１．・・・、ｔ
ｔｃｔを選び、 ｔｉｊ −” ｒｉ ｊ２ｍｏｄ
ｍあるいはｊｉｊ−”Ａｒｌｊ２ｍｏｄｍを満たすｒｉ
ｌ ＊ ””、ｒｉｄ とを演算装置（７）を用いて
計算する。
ａｄ ｍを満たすｒを演算装置（７）を用いて計算する
。もしもＴ−ＺとＳ−Ｚの大きさがｄだけ違う場合、確
認者ＢはＴ−ＺとＳ−Ｚの大きい方の集合から、乱数発
生器を用いてランダムにｄ個の集合ｔ１１．・・・、ｔ
ｔｃｔを選び、 ｔｉｊ −” ｒｉ ｊ２ｍｏｄ
ｍあるいはｊｉｊ−”Ａｒｌｊ２ｍｏｄｍを満たすｒｉ
ｌ ＊ ””、ｒｉｄ とを演算装置（７）を用いて
計算する。
ステップ１５：確認者は前記ｒｉ１．・・・＋ ’ｉｄ
を通信回線（５）を通して、証明者に送る。
を通信回線（５）を通して、証明者に送る。
ステップ１６：証明者は前記ｒｉ１＊・・・、ｒｉｄが
ｔｉｊ ：ｌ： ｒｉｊ２ｍｏｄ ｍあるいはｔ１ｊ＝
ａｒｉ」２ｎｏｄ ｍを満たすかどうかを確かめる。
ｔｉｊ ：ｌ： ｒｉｊ２ｍｏｄ ｍあるいはｔ１ｊ＝
ａｒｉ」２ｎｏｄ ｍを満たすかどうかを確かめる。
ステップ１Ｔ：確認者は
Ｘ ”Ｔ Ｚ （ｔｔｌ、 −、ｔｆｄ ）ｙ＝ｓ
−ｚ −（ｔｌｌ、 ・・°、 ｔｔｄ）と置き。
−ｚ −（ｔｌｌ、 ・・°、 ｔｔｄ）と置き。
Ｃｘ二〇すなわちｘ：ｒｏｒｎｏｄｍならば。
Ｘ’ ＝ （ｒ（Ｉｒｉ ＝： 辰ｍａｄ ｍ ｌ ｔ
ｉεＸ）Ｙ’ ＝（ｙｒｏｒｉ ＝ ２ ｍｏｃ！
ｍ １ｔｉｌＥＹ ）ＣＸ＝１すなわち１”Ｙｒｃ３
ｍｏｄｍならば。
ｉεＸ）Ｙ’ ＝（ｙｒｏｒｉ ＝ ２ ｍｏｃ！
ｍ １ｔｉｌＥＹ ）ＣＸ＝１すなわち１”Ｙｒｃ３
ｍｏｄｍならば。
Ｘ ＝ （）’ｒｏｒｉ ＝Ｍ ｎｏｄ ｍ ＩＪεＸ
）Ｙ’＝ （ｒｏｒｉ ＝ Ｆ口ｎｏｄ ｍ ｌ Ｊｆ
ＥＹ ）を演算装置（７）を用いて求める。
）Ｙ’＝ （ｒｏｒｉ ＝ Ｆ口ｎｏｄ ｍ ｌ Ｊｆ
ＥＹ ）を演算装置（７）を用いて求める。
ステップ１８：確認者は乱数発生器（８）を用いてＸ″
′Ｙ′の元をランダムな順序で通信回線（５）を通して
、証明者に送る。
′Ｙ′の元をランダムな順序で通信回線（５）を通して
、証明者に送る。
ステップ１９．証明者は前記確認者より送られるｘ／
’−’ ｙ／ の元が正しい形であるかを確かめる。す
なわちＸ″′Ｙ′ の任意の元Ｗが、あるＸ″″Ｙの
任意の元ｔ１ に対して ｗ２＝ｘｔ１ｍｏｄｍ あるいは ｗ” ＝ ｙｘ ｔ ｉ ｍｏｄ ｍ が成立するか、かつまた ｌｘ”ｙ’ｌ＞ ｎ ／ ３ であるかを演算装置（３）を用いて確かめる。
’−’ ｙ／ の元が正しい形であるかを確かめる。す
なわちＸ″′Ｙ′ の任意の元Ｗが、あるＸ″″Ｙの
任意の元ｔ１ に対して ｗ２＝ｘｔ１ｍｏｄｍ あるいは ｗ” ＝ ｙｘ ｔ ｉ ｍｏｄ ｍ が成立するか、かつまた ｌｘ”ｙ’ｌ＞ ｎ ／ ３ であるかを演算装置（３）を用いて確かめる。
ステップ２０ ：証明者は前記判定結果が正しければ、
ｖ＝Ｑｍ（ｘ） を通信回線（５）を通して、確認者
に送る。正しくなければ操作を中止する。
ｖ＝Ｑｍ（ｘ） を通信回線（５）を通して、確認者
に送る。正しくなければ操作を中止する。
ステップ２１ ：確認者はｖ ” ＣＸ であるか否
かを演算装置（７）を用いて確かめる。ｖ ＝Ｃエ な
らばステップ６に戻る。ｖ ＊ Ｃ１ならば確認者は操
作を中止する。
かを演算装置（７）を用いて確かめる。ｖ ＝Ｃエ な
らばステップ６に戻る。ｖ ＊ Ｃ１ならば確認者は操
作を中止する。
従来の方式は以上のように構成されているので。
証明者は確認者に対して、ステップ１でおくる乱数ａが
平方非剰余数であるということ以外、何の情報も漏らす
ことなく、Ｑｍを計算する能力を所有することを納得さ
せることが可能であるが９ｍの素因数を知らない確認者
にとって乱数ａが平方非剰余数であるという情報は確認
者自身では得ることができないことを考えると、この装
置を用いた認証方式は乱数ａが平方非剰余数であるとい
う重要な情報が確実に洩れるという問題があった。
平方非剰余数であるということ以外、何の情報も漏らす
ことなく、Ｑｍを計算する能力を所有することを納得さ
せることが可能であるが９ｍの素因数を知らない確認者
にとって乱数ａが平方非剰余数であるという情報は確認
者自身では得ることができないことを考えると、この装
置を用いた認証方式は乱数ａが平方非剰余数であるとい
う重要な情報が確実に洩れるという問題があった。
この発明はこうし友ある特定の数が平方非剰余数である
といった重要な情報を漏らさずに、証明者がＱｍを計算
する能力を所有すること全確認者にたいして納得させる
安全かつ信頼性の高い認証システムを得ることを目的と
する。
といった重要な情報を漏らさずに、証明者がＱｍを計算
する能力を所有すること全確認者にたいして納得させる
安全かつ信頼性の高い認証システムを得ることを目的と
する。
この発明に係る認証方式は、証明者の操作により乱数を
発生する証明者側乱数発生器と、証明者の操作によシ演
算を行う証明者側演算器と、証明者の操作により与えら
れた正整数が法Ｎのもとて平方剰余であるか、平方非剰
余であるかの判定を行う判定器と、上記証明者側乱数発
生手段によシ生成される乱数や上記証明者側演算手段に
より得られる計算結果や確認者より送られるデータを蓄
える記憶装置と、確認者の操作にょシ乱数を発生する確
認者側乱数発生器と、確認者の操作により演算を行う確
認者側演算器と、上記確認者側乱数発生手段によシ生成
される乱数や上記確認者側演算手段により得られる計算
結果や証明者より送られるデータを蓄える記憶装置とを
備え、証明者側装置と確認者側装置との間で相互に通信
を行う通信回線と証明者が確認者に複数の平方非剰余数
の中にただ１つの平方剰余数を入れ、平方剰余数の位置
は確認者に教えないという認証データを確認者に送り、
この認証データを用いて質疑応答を繰返すことを手段と
して認証者は証明者が本当に平方剰余であるか平方非剰
余であるかの判定を効率よく計算するアルゴリズムをし
っている。ある込は計算装置を有するということを確か
めるものである。
発生する証明者側乱数発生器と、証明者の操作によシ演
算を行う証明者側演算器と、証明者の操作により与えら
れた正整数が法Ｎのもとて平方剰余であるか、平方非剰
余であるかの判定を行う判定器と、上記証明者側乱数発
生手段によシ生成される乱数や上記証明者側演算手段に
より得られる計算結果や確認者より送られるデータを蓄
える記憶装置と、確認者の操作にょシ乱数を発生する確
認者側乱数発生器と、確認者の操作により演算を行う確
認者側演算器と、上記確認者側乱数発生手段によシ生成
される乱数や上記確認者側演算手段により得られる計算
結果や証明者より送られるデータを蓄える記憶装置とを
備え、証明者側装置と確認者側装置との間で相互に通信
を行う通信回線と証明者が確認者に複数の平方非剰余数
の中にただ１つの平方剰余数を入れ、平方剰余数の位置
は確認者に教えないという認証データを確認者に送り、
この認証データを用いて質疑応答を繰返すことを手段と
して認証者は証明者が本当に平方剰余であるか平方非剰
余であるかの判定を効率よく計算するアルゴリズムをし
っている。ある込は計算装置を有するということを確か
めるものである。
証明者は乱数発生器と演算器とを用いて複数の平方非剰
余数の中にただ１つの平方剰余数を入れた認証データを
構成し確認者に送る。確認者は乱数発生器と演算器とを
用いて証明者から送られる認証データを基にランダムに
認証データを巡回置換し、さらに各成分に平方剰余を掛
合せ九質問データを構成し証明者に送る。証明者は確認
者が正しく質問データを送っていることを、確認者との
通信によシ確かめたうえで０判定装置を用いて確認者か
ら送られる質問データに対する巡回置換の位数を解答デ
ータとして確認者に送り返す。確認者は証明者から送ら
れる解答データが正しいかどうかで認証を行う。
余数の中にただ１つの平方剰余数を入れた認証データを
構成し確認者に送る。確認者は乱数発生器と演算器とを
用いて証明者から送られる認証データを基にランダムに
認証データを巡回置換し、さらに各成分に平方剰余を掛
合せ九質問データを構成し証明者に送る。証明者は確認
者が正しく質問データを送っていることを、確認者との
通信によシ確かめたうえで０判定装置を用いて確認者か
ら送られる質問データに対する巡回置換の位数を解答デ
ータとして確認者に送り返す。確認者は証明者から送ら
れる解答データが正しいかどうかで認証を行う。
以下、この発明の一実施例を詳しく説明する。
第」図は、この発ＩＪｊ［係る認証方式の一実樒例を示
すブロック図である。図において、 （１０１）は証
明者の操作により乱数を生成する乱数発生器。
すブロック図である。図において、 （１０１）は証
明者の操作により乱数を生成する乱数発生器。
（１０２）は証明者の操作により、乱数発生器より生成
される乱数や演算装置より出力される演算結果や、認証
者よシ送られるデータを記憶するメモリ。
される乱数や演算装置より出力される演算結果や、認証
者よシ送られるデータを記憶するメモリ。
（１０３）は証明者の操作により演算を行う演算装置。
（１０４）は証明者の操作によりＱｍの計算を行い。
与えられた数が平方剰余であるか否かの判定を行う判定
装置、 （１０５）は証明者と確認者が用いる通信回
線、 （１０６）は確認者の操作により、乱数発生器
より生成される乱数や演算装置よシ出力される演算結果
や、確認者より送られるデータを記憶するメモ！、Ｉ、
（１０７）は確認者の操作によシ演算を行う演算装
置である。
装置、 （１０５）は証明者と確認者が用いる通信回
線、 （１０６）は確認者の操作により、乱数発生器
より生成される乱数や演算装置よシ出力される演算結果
や、確認者より送られるデータを記憶するメモ！、Ｉ、
（１０７）は確認者の操作によシ演算を行う演算装
置である。
上述したような装置構成は例えばＩＣカードと計算機シ
ステムにより実現される。
ステムにより実現される。
次に動作について説明する。
ステップ１：ｆ間者は乱数発生器（１０１）を用いて正
整数の乱数ａを生成しメモＩＪ （１０２）に記憶する
。
整数の乱数ａを生成しメモＩＪ （１０２）に記憶する
。
ステップ２：証明者は前記乱数ａをメモＩＪ （１０２
）より呼び出し、乱数ａがｍと互いに素であるか否かす
なわち （ａ、ｎ’＋）＝１ を満たすか否か、演算装置（１０５）を用いて判定する
。（ａ、ｍ）＝１であればステップ３へ、（−、ｍ）＃
１でちればステップ１へ戻る。
）より呼び出し、乱数ａがｍと互いに素であるか否かす
なわち （ａ、ｎ’＋）＝１ を満たすか否か、演算装置（１０５）を用いて判定する
。（ａ、ｍ）＝１であればステップ３へ、（−、ｍ）＃
１でちればステップ１へ戻る。
ステップ３：証明者１−ｊ＠記乱数ａをメモＩＪ （１
０２）より呼び出し、乱数＆の法ｍのもとてのヤコビ記
号が１であるか否かすなわち （ａ／ｍ）＝１ を満たすか否か、演算装置（１０３）を用いて判定する
。（ａ／ｍ）＝１であればステップ４へ、（ａ／ｍ）＝
−１であれはステップ１へ戻る。
０２）より呼び出し、乱数＆の法ｍのもとてのヤコビ記
号が１であるか否かすなわち （ａ／ｍ）＝１ を満たすか否か、演算装置（１０３）を用いて判定する
。（ａ／ｍ）＝１であればステップ４へ、（ａ／ｍ）＝
−１であれはステップ１へ戻る。
ステップ４：証明者は前記乱数ａをメモｌ） （１０２
）より呼び出し、乱数ａが平方非剰余であるか否かすな
わち Ｑｍ （ａ） ＝ ０ を満たすか否か０判定装置（１０４）を用いて判定する
。Ｑｍ （ａ） ＝ ０ であればステップ５ ヘ、
Ｑｍ（ａ） ＝：１であればステップ１へ戻る。
）より呼び出し、乱数ａが平方非剰余であるか否かすな
わち Ｑｍ （ａ） ＝ ０ を満たすか否か０判定装置（１０４）を用いて判定する
。Ｑｍ （ａ） ＝ ０ であればステップ５ ヘ、
Ｑｍ（ａ） ＝：１であればステップ１へ戻る。
ステップ５：証明者は乱数発生器（１０１）と演算装置
（１０３）とを用いて正整数の乱数を成分とするｑ行ｐ
列の乱数行列Ｒ＝（ｒｉｊ）Ｏ≦ｌ≦ｐ−ｔ、ｏ≦ｊ≦
ｑ−Ｌ（ただし各ｒｉｊはｍと互いに素）を生成レモリ
（１０２）に記憶する。
（１０３）とを用いて正整数の乱数を成分とするｑ行ｐ
列の乱数行列Ｒ＝（ｒｉｊ）Ｏ≦ｌ≦ｐ−ｔ、ｏ≦ｊ≦
ｑ−Ｌ（ただし各ｒｉｊはｍと互いに素）を生成レモリ
（１０２）に記憶する。
ステップ６：証明者は乱数発生器（１０１）を用いて整
数の乱数ベクトルＢ＝（ｂｏ、・・・＊ ｂｑ−１）
（０≦ｂｊ≦ｐ−１）を生成しメモリ（１０２）に記憶
する。
数の乱数ベクトルＢ＝（ｂｏ、・・・＊ ｂｑ−１）
（０≦ｂｊ≦ｐ−１）を生成しメモリ（１０２）に記憶
する。
ステップ７：証明者は、前記正整数の乱数ベクトルＢと
前記平方非剰余である正整数の乱数ａと乱数行列Ｒとを
メモリ（１［１１）より呼び出し、演算装置（１０５）
を用いて。
前記平方非剰余である正整数の乱数ａと乱数行列Ｒとを
メモリ（１［１１）より呼び出し、演算装置（１０５）
を用いて。
を計算し、認証データｓ ＝（８Ｉｊ） ｏ≦ｉ≦ｐ−
１゜０≦ｊ≦ｑ−ｔ を構成しメモ’） （１０２）
に記憶する。
１゜０≦ｊ≦ｑ−ｔ を構成しメモ’） （１０２）
に記憶する。
ステップ８：証明者は、前記認証データＳをメモＩＪ
（１０２）より呼び出し９通信回線（１０５）を通して
通信相手となる確認者に送る。
（１０２）より呼び出し９通信回線（１０５）を通して
通信相手となる確認者に送る。
ステップ９：確認者は前記証明者よシ送られる認証デー
タＳをメモリ（１０６）に記憶し、認証データＳの各Ｓ
ｉｊ のヤコビ記号（ｓ ｔ Ｊ／ Ｎ ）が１であ
るかどうかを演算装置（１０７）を用いて確かめる。
タＳをメモリ（１０６）に記憶し、認証データＳの各Ｓ
ｉｊ のヤコビ記号（ｓ ｔ Ｊ／ Ｎ ）が１であ
るかどうかを演算装置（１０７）を用いて確かめる。
以下のステップ１０〜ステツプ２１ ヲｎ＝ｌｏｇ２ｍ
回繰り返す。
回繰り返す。
ステップ１０：確認者は乱数発生器（１０８）とを用い
て整数の乱数ベクトルＣ＝（ｃｏ、・・・、ｃｌ）一 （０≦ｅｊ≦ｐ〜１）と正整数の乱数を成分とするｑ行
ｐ列の乱数行列Ｔ＝（ｔｆｊ）０≦ｉ≦ｐ−１，０≦ｊ
≦ｑ−１を生成しメモリ（１０６）に記憶する。
て整数の乱数ベクトルＣ＝（ｃｏ、・・・、ｃｌ）一 （０≦ｅｊ≦ｐ〜１）と正整数の乱数を成分とするｑ行
ｐ列の乱数行列Ｔ＝（ｔｆｊ）０≦ｉ≦ｐ−１，０≦ｊ
≦ｑ−１を生成しメモリ（１０６）に記憶する。
ステップ１１：確認者は、前記証明者よシ送られる認証
データＳと前記確認者側乱数発生器（１０８）が生成し
た乱数ベクトルＣ１乱数行列Ｔとをメモ’） （１０６
）よシ呼び出し演算装置（ｉｏ７）を用いて。
データＳと前記確認者側乱数発生器（１０８）が生成し
た乱数ベクトルＣ１乱数行列Ｔとをメモ’） （１０６
）よシ呼び出し演算装置（ｉｏ７）を用いて。
Ｇ （ｉ、 ｊ ）＝＝（ｉ ＋ａｊｒｒｉｏｄ ｐ、
ｊ 、）ｕｉｊ”５Ｇ（ｉ、ｊ） ・ Ｖｉｊ””ｔｉｊ２Ｘｕｉｊ ｒｎｏｄＮを計算し、質
問データｖ＝（ｖｉｊ）ｏ≦ｉ≦ｐ−１゜０≦ｊ≦ｑ−
１を構成しメモリ（１０６）に記憶する。
ｊ 、）ｕｉｊ”５Ｇ（ｉ、ｊ） ・ Ｖｉｊ””ｔｉｊ２Ｘｕｉｊ ｒｎｏｄＮを計算し、質
問データｖ＝（ｖｉｊ）ｏ≦ｉ≦ｐ−１゜０≦ｊ≦ｑ−
１を構成しメモリ（１０６）に記憶する。
ステップ１２：確認者は前記質問データ■をメモリ（１
０６）より呼び出し１通信回ｌ５（１０５）を通して証
明者に送る。
０６）より呼び出し１通信回ｌ５（１０５）を通して証
明者に送る。
ステップ１３：証明者は乱数発生器（，０１）を用いて
ランダムに（ｏ、１．・・・、 ｑ−１） の中から
Ｗ個の数（ｅｏ、・・・、ｅｗ−１）（但し６１＃６ｊ
）を選び、確認データＥ ＝（ｅｏ 、 ”・、 ｅ
ｗ−１） ’に構成シメモリ（１０２）に記憶する。
ランダムに（ｏ、１．・・・、 ｑ−１） の中から
Ｗ個の数（ｅｏ、・・・、ｅｗ−１）（但し６１＃６ｊ
）を選び、確認データＥ ＝（ｅｏ 、 ”・、 ｅ
ｗ−１） ’に構成シメモリ（１０２）に記憶する。
ステップ１４：証明者は、＠記乱数ベクトルＥをメモリ
（１０２）より呼び出し１通信回ｌ （１０５） を通
して確認者に送る。。
（１０２）より呼び出し１通信回ｌ （１０５） を通
して確認者に送る。。
ステップ１５．確認者は、前記証明者より送られる確認
データＥ＝（ｅｏ、 ・・・＋ｅＷ−１）をメモリ（１
０６）に記憶し、Ｅの各Ｑ ｊ に対する変換データＴ
ＣＥ〕＝ （ｔｉｊ） ０≦ｉ≦ｐ −４、ｊ ＥＦ
Ｃ’ ［Ｅ’）＝ （ｅｊ） ｊＥＥ をメモリ（１０６）より呼び出し０通信回線（１０５）
を通して証明者に送る。
データＥ＝（ｅｏ、 ・・・＋ｅＷ−１）をメモリ（１
０６）に記憶し、Ｅの各Ｑ ｊ に対する変換データＴ
ＣＥ〕＝ （ｔｉｊ） ０≦ｉ≦ｐ −４、ｊ ＥＦ
Ｃ’ ［Ｅ’）＝ （ｅｊ） ｊＥＥ をメモリ（１０６）より呼び出し０通信回線（１０５）
を通して証明者に送る。
ステップ１６：証明者は、＠記確認者より送られる変換
データをメモＵ （１０２）に記憶し、変換データが正
当であるかどうか、すなわち Ｇ （ｔ、 ｊ）＝＝（ｉ＋ｃｊｍｎｄ ｐ、 ｊ）
ｕｌｊ” ５Ｇ（Ｌ Ｊ ）・ ｖｉｊ”” ｔＢ２Ｘ ｕｌ ｊｍａｄ Ｎがすべての
Ｏ≦ｉ≦ｒｓ−ｔ、ｊＥＥに対して成立するかどうかを
演算装置（１０３）を用いて確かめる。
データをメモＵ （１０２）に記憶し、変換データが正
当であるかどうか、すなわち Ｇ （ｔ、 ｊ）＝＝（ｉ＋ｃｊｍｎｄ ｐ、 ｊ）
ｕｌｊ” ５Ｇ（Ｌ Ｊ ）・ ｖｉｊ”” ｔＢ２Ｘ ｕｌ ｊｍａｄ Ｎがすべての
Ｏ≦ｉ≦ｒｓ−ｔ、ｊＥＥに対して成立するかどうかを
演算装置（１０３）を用いて確かめる。
ステップ１１：証明者はランダムに（ｅＯ＊・・・。
”Ｗ−１１を除＜ （０，１，−、ｑ−１１の中からｈ
を選ヒ、メモリ（１０２）に記憶する。
を選ヒ、メモリ（１０２）に記憶する。
ステップ１８：証明者は確認者から送られる質問データ
Ｖのｈ行の各Ｖｉｊが平方剰余であるか否かを判定し、
平方剰余である位置をｄｈ（０≦ｄ≦ｐ−１）とし、メ
モリ（１０２）に記憶する。
Ｖのｈ行の各Ｖｉｊが平方剰余であるか否かを判定し、
平方剰余である位置をｄｈ（０≦ｄ≦ｐ−１）とし、メ
モリ（１０２）に記憶する。
ステップ１９：証明者は、前記演算手段により得られる
演算結果ｄｈ と前記乱数ｂｈ とをメモリ（１０２
）より呼び出し、演算装（１００３）を用いて０ｒｄｈ
＝ｄｈ−ｂｈｎ＋ｏｄ ｐ を計算し判定データ（ｈ 、 ０ｒｄｈ）を構成し、メ
モリ（１０２）に記憶する。
演算結果ｄｈ と前記乱数ｂｈ とをメモリ（１０２
）より呼び出し、演算装（１００３）を用いて０ｒｄｈ
＝ｄｈ−ｂｈｎ＋ｏｄ ｐ を計算し判定データ（ｈ 、 ０ｒｄｈ）を構成し、メ
モリ（１０２）に記憶する。
ステップ２０：証明者は前記判定データ（ｈ。
０ｒｄｈ）をメモ！Ｊ、（１０２）より呼び出し２通信
回線（１０５）を通して確認者に送る。
回線（１０５）を通して確認者に送る。
ステップ２１：確認者は、前記乱数Ｃｈをメモリ（１０
６）より呼び出し、乱数Ｃｈ と証明者から送られる前
記０ｒｄｈが一致するかを確かめる。
６）より呼び出し、乱数Ｃｈ と証明者から送られる前
記０ｒｄｈが一致するかを確かめる。
なお上記実施例において証明者、確認者で説明したが、
ＩＣカードと端末のように同等の対象によシ実現される
ことは言うまでもない。
ＩＣカードと端末のように同等の対象によシ実現される
ことは言うまでもない。
以上、詳述したように、この発明は証明者が確認者に複
数の平方非剰余数の中にただ１つの平方剰余数を入れた
認証データを送る。但し平方剰余数の位置は教えなめこ
とで、この認証データを用いて確認者は、証明者が本当
に平方剰余であるか平方非剰余であるかの判定を効率よ
く計算するアルゴリズムをしっている。あるいは計算装
置を有するということを質疑応答を繰返すことで確かめ
るので、確認者がこの認証システムを用いて、正当な証
明者から得る情報は、初めに証明者から送られる認証デ
ータの中にただ１つ平方剰余数が存在するということで
あって、どの元が平方剰余数であるか、あるいは平方非
剰余数であるかという情報は得ることはできない。した
がって証明者は従来のＧＭＲの方式を用いた認証装置に
くらべて有益な情報を漏らさず安全性の高い、認証を行
うことが可能となる。
数の平方非剰余数の中にただ１つの平方剰余数を入れた
認証データを送る。但し平方剰余数の位置は教えなめこ
とで、この認証データを用いて確認者は、証明者が本当
に平方剰余であるか平方非剰余であるかの判定を効率よ
く計算するアルゴリズムをしっている。あるいは計算装
置を有するということを質疑応答を繰返すことで確かめ
るので、確認者がこの認証システムを用いて、正当な証
明者から得る情報は、初めに証明者から送られる認証デ
ータの中にただ１つ平方剰余数が存在するということで
あって、どの元が平方剰余数であるか、あるいは平方非
剰余数であるかという情報は得ることはできない。した
がって証明者は従来のＧＭＲの方式を用いた認証装置に
くらべて有益な情報を漏らさず安全性の高い、認証を行
うことが可能となる。
第１図は本発明の認証方式を実現する装置の構成をあら
れすブロック図、第２図は従来装置の構成をあられすブ
ロック図である。 ＜１１は証明者側乱数発生器、（２）は証明者側メモリ
。 （３）は証明者側演算装置、（４）は証明者判定装置、
（５）は通信回線、（６）は確認者側メモ！Ｊ、（７）
は確認者側演算装置、（８）は確認者側乱数発生器、
（１０１）は証明者側乱数発生器、 （１０２）は
証明者側メモリ。 （１０３）は証明者側演算装置、 （１０４）は証明者
判定装置、 （１０５）は通信回線、 （１０６）
は確認者側メモ！Ｊ、 （１０７）は確認者側演算装
置、 （１０８）は確認者側乱数発生器を表す。
れすブロック図、第２図は従来装置の構成をあられすブ
ロック図である。 ＜１１は証明者側乱数発生器、（２）は証明者側メモリ
。 （３）は証明者側演算装置、（４）は証明者判定装置、
（５）は通信回線、（６）は確認者側メモ！Ｊ、（７）
は確認者側演算装置、（８）は確認者側乱数発生器、
（１０１）は証明者側乱数発生器、 （１０２）は
証明者側メモリ。 （１０３）は証明者側演算装置、 （１０４）は証明者
判定装置、 （１０５）は通信回線、 （１０６）
は確認者側メモ！Ｊ、 （１０７）は確認者側演算装
置、 （１０８）は確認者側乱数発生器を表す。
Claims (2)
- （１）認証通信を行うシステムにおいて、証明者は、証
明者が生成した乱数に演算を施し認証データを構成し、
この認証データを確認者へ送り、確認者は、認証データ
と確認者が生成した乱数とに演算を施し、質問データを
構成しこの質問データを証明者へ送り、証明者は、確認
者から送られる認証データに応じた解答データを確認者
へ送り、確認者は証明者から送られる解答データが正し
いかを確かめることにより認証を行うことを特徴とする
認証方式。 - （２）請求項１に記載の認証方式において、証明者が確
認者より質問データを受け取つた後、証明者は、証明者
が生成した乱数に演算を施し確認データを構成し確認者
へ送り、確認者は、証明者より送られる確認データに応
じて、認証データから質問データを構成した時に用いた
変換データを証明者に送り、証明者は、確認者から送ら
れる変換データと認証データとより、確認データに対応
する質問データが正答かどうかを確かめ、証明者は、確
認者から送られる認証データに応じた解答データを確認
者へ送ることを特徴とする認証方式。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1125224A JPH02305039A (ja) | 1989-05-18 | 1989-05-18 | 認証方式 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP1125224A JPH02305039A (ja) | 1989-05-18 | 1989-05-18 | 認証方式 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH02305039A true JPH02305039A (ja) | 1990-12-18 |
Family
ID=14904911
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1125224A Pending JPH02305039A (ja) | 1989-05-18 | 1989-05-18 | 認証方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH02305039A (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07212356A (ja) * | 1993-12-30 | 1995-08-11 | Internatl Business Mach Corp <Ibm> | 通信パートナの認証方法及びシステム |
-
1989
- 1989-05-18 JP JP1125224A patent/JPH02305039A/ja active Pending
Non-Patent Citations (2)
| Title |
|---|
| K OHTA T OKAMOTO PRACTICAL EXTENSION OF FIAT-SHAMIR SCHEME ELECTRONICS LETTERS=1988 * |
| U FEIGE A FIAT A SHAMIR ZERO KNOWLEDGE PROOFS OF IDENTITY PROCEEDINGS OF 19TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING=1987 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH07212356A (ja) * | 1993-12-30 | 1995-08-11 | Internatl Business Mach Corp <Ibm> | 通信パートナの認証方法及びシステム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| EP0824814B1 (en) | Methods and apparatus for authenticating an originator of a message | |
| JP2671649B2 (ja) | 認証方式 | |
| Lyubashevsky | Lattice-based identification schemes secure under active attacks | |
| EP3146670B1 (en) | Network authentication system with dynamic key generation | |
| EP0348812B1 (en) | Authentication method and apparatus therefor | |
| CN115632786B (zh) | 基于双环的适配器签名方法 | |
| CN106936566B (zh) | 一种基于区块链技术的可外包的文书签署方法 | |
| CN109067801A (zh) | 一种身份认证方法、身份认证装置及计算机可读介质 | |
| CN105827620B (zh) | 一种数据传输系统及其方法 | |
| US7313697B2 (en) | Method for authentication | |
| JP2000358027A (ja) | 認証情報の認証確認用システム | |
| CN103338202B (zh) | 一种基于智能卡的远程用户密码双重验证方法 | |
| WO2002009348A3 (en) | Ring-based digital signature and authentication method and apparatus | |
| CN107911217B (zh) | 基于ecdsa算法协同生成签名的方法、装置和数据处理系统 | |
| WO2007133274B1 (en) | Centralized identity verification and/or password validation | |
| CN108900309A (zh) | 一种鉴权方法及鉴权系统 | |
| Tian et al. | Pribioauth: Privacy-preserving biometric-based remote user authentication | |
| JP4945026B2 (ja) | 減少した計算組を伴う認証または署名プロセス | |
| JP2007519044A (ja) | ゼロ知識証明暗号方法及び装置 | |
| Simmons | A protocol to provide verifiable proof of identity and unforgeable transaction receipts | |
| Breuer et al. | Cryptocurrencies with security policies and two-factor authentication | |
| CN100380862C (zh) | 验证实体真实性或消息完整性的方法、系统、设备 | |
| Lal et al. | Authentication schemes using braid groups | |
| JPH02305039A (ja) | 認証方式 | |
| CN115150163A (zh) | 一种匿名电子投票方法及装置、存储介质及电子设备 |