JPH1165439A - Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体 - Google Patents

Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体

Info

Publication number
JPH1165439A
JPH1165439A JP9156903A JP15690397A JPH1165439A JP H1165439 A JPH1165439 A JP H1165439A JP 9156903 A JP9156903 A JP 9156903A JP 15690397 A JP15690397 A JP 15690397A JP H1165439 A JPH1165439 A JP H1165439A
Authority
JP
Japan
Prior art keywords
data
value
ary
digit
authenticator
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
Application number
JP9156903A
Other languages
English (en)
Inventor
Takeshi Takagi
剛 高木
Shozo Naito
昭三 内藤
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
NTT Inc
Original Assignee
Nippon Telegraph and Telephone Corp
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Nippon Telegraph and Telephone Corp filed Critical Nippon Telegraph and Telephone Corp
Priority to JP9156903A priority Critical patent/JPH1165439A/ja
Priority to CA002212664A priority patent/CA2212664C/en
Priority to EP97113746A priority patent/EP0823802A3/en
Priority to US08/907,852 priority patent/US6259790B1/en
Publication of JPH1165439A publication Critical patent/JPH1165439A/ja
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/30—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
    • H04L9/3006—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters
    • H04L9/302—Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy underlying computational problems or public-key parameters involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L9/00—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols
    • H04L9/32—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials
    • H04L9/3247—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures
    • H04L9/3249—Cryptographic mechanisms or cryptographic arrangements for secret or secure communications; Network security protocols including means for verifying the identity or authority of a user of the system or for message authentication, e.g. authorization, entity authentication, data integrity or data verification, non-repudiation, key authentication or verification of credentials involving digital signatures using RSA or related signature schemes, e.g. Rabin scheme

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Security & Cryptography (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Storage Device Security (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

(57)【要約】 【課題】 従来の公開鍵暗号と同等の強度を持ちながら
復号化速度を高めた暗号化通信方法及び認証方法を提供
する。 【解決手段】 暗号化装置３１の平文分割処理部３３
は、平文データをそれぞれ公開鍵ｎの剰余類の範囲内の
ｋ個のブロックＭ0,Ｍ1,…Ｍk-1に分割し、データ結合
処理部３５は、この各ブロックをｋ桁のｎ進数、Ｍ
（ｎ）＝Ｍ0＋ｎＭ1＋…ｎk-1Ｍk-1として表現する。暗
号化処理部３７は、Ｃ≡（Ｍ（ｎ））e≡（Ｍ0＋ｎＭ1
＋…ｎk-1Ｍk-1）e（mod ｎk）により暗号化する。復号
化装置４１の最下位桁復号化処理部４３は、Ｍ0≡
（Ｃ）d≡（Ｍ0＋ｎＭ1＋…ｎk-1Ｍk-1）d（modｎ）に
より最下位桁Ｍ0を復号化し、上位桁復号化処理部４５
は既に求められた下位桁の値を用いて同一の計算式を繰
り返し、再帰的に順次上位桁の復号を行う。データ連結
処理部４７は、復号化された各ブロックを連結して平文
を復元する。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、暗号化鍵が公開さ
れ、復号化鍵のみが秘匿される公開鍵方式の暗号に係
り、特に、従来のリベスト・シャミール・アドルマン暗
号（以下、ＲＳＡ暗号と略す）やラビン暗号と同等の強
度を保ちながら、復号化の速度を向上させた公開鍵暗号
による通信および認証方式並びにそれらの装置に関す
る。
【０００２】また、本発明は、ＲＳＡ暗号やラビン暗号
の欠陥である、同じ平文を複数の通信相手に送る場合
（同報通信）、２個の平文に多項式関係がある場合、平
文のビット数が小さい場合など、暗号が簡単に破られて
しまうという点を克服し、より安全である公開鍵暗号に
よる通信および認証方式並びそれらの装置に関する。
【０００３】
【従来の技術】電気通信において、通信内容の盗聴を防
ぎ、改竄を検出するために暗号技術は不可欠である。特
に、鍵管理が簡便な公開鍵暗号が有効であり、広く利用
されつつある。代表的な公開鍵暗号のアルゴリズムとし
て、冪（べき）乗剰余演算を用いるＲＳＡ暗号、二つの
素数の積を法とした２次多項式を暗号化関数に持つラビ
ン暗号等があり、既に実用化されている。
【０００４】次に、ＲＳＡ暗号、ラビン暗号の順で従来
技術を簡略に説明する（参考文献１：「現代暗号理論」
電子情報通信学会発行、１９８６）。
【０００５】なお、以下の記載において、（ｍｏｄ
Ｎ）はＮを法とする演算、≡は合同、ＬＣＭは最小公倍
数、ＧＣＤは最大公約数、［Ａ］はＡを超えない最大整
数を示すガウス記号、√（Ｂ）はＢの平方根をそれぞれ
示すものとする。
【０００６】〔ＲＳＡ暗号の基本原理〕ＲＳＡ暗号の暗
号化鍵は（ｅ，Ｎ）の組であり、対応する復号化鍵は
（ｄ，Ｎ）の組である。ｅとＮとは公開鍵であり、ｄは
秘密鍵である。Ｎは２つの素数、ｐ、ｑの積（Ｎ＝ｐ
ｑ）であり、Ｎを生成するｐ，ｑの組も秘密鍵と呼ばれ
ることがある。平文をＭ、暗号文をＣとする。
【０００７】暗号化Ｅと復号化Ｄのアルゴリズムは、次
の式（１）および式（２）で表される。
【０００８】
【数１】 Ｃ＝Ｅ（Ｍ）＝Ｍe （ mod Ｎ） …（１） Ｍ＝Ｄ（Ｃ）＝Ｃd （ mod Ｎ） …（２） 但し、ＭとＣとは０からＮ−１の間の整数である。もし
元のメッセージがＮより大きければ、サイズＮのブロッ
クに分割して逐一、暗号化・復号化を適用すればよい。
【０００９】暗号化と復号化は、１対１かつ上への写像
である。従って、ＭとＣを代表してＭで表すと、
【数２】 Ｄ（Ｅ（Ｍ））＝Ｅ（Ｄ（Ｍ））＝Ｍ …（３） 式（３）が成立する。具体的には、
【数３】 Ｍed≡Ｍ （ mod Ｎ） …（４） 式（４）が成立する。式（４）がすべてのＭに対して成
立するような、暗号鍵ｅ，ｄ，Ｎの生成手順は以下のと
おりである。
【００１０】〔ＲＳＡ暗号の鍵生成〕まず、任意の相異
なる二つの大きな素数ｐ，ｑを選び、その積Ｎ＝ｐｑを
計算する（第１段階）。
【００１１】次いで、（ｐ−１）と（ｑ−１）の最小公
倍数Ｌを計算し、Ｌと互いに素でＬより小さな任意の整
数ｅを選ぶ（第２段階）。
【００１２】
【数４】 Ｌ＝ＬＣＭ（ｐ−１，ｑ−１） …（５） ＧＣＤ（ｅ，Ｌ）＝１， １＜ｅ＜Ｌ …（６） 次いで、第２段階で求めたｅとＬをもとに、次の合同式
（７）を解き、ｄを求める（第３段階）。
【００１３】
【数５】 ｅｄ≡１ （ mod Ｌ） …（７） 式（７）からｄを求めるには、ユークリッドの互除法を
用いればよい。また、前記の生成手順は、まず、第２段
階でｅを先に選び、第３段階でｄを計算しているが、逆
にｄを先に選び、後でｅを計算してもよい。
【００１４】〔ＲＳＡ暗号による認証〕ＲＳＡ暗号によ
る認証通信は、以下のようにして行われる。まず、送信
者は、認証文Ｍをハッシュ関数ｈによりハッシュ化し、
認証子ｈ（Ｍ）を得る。次いで認証子ｈ（Ｍ）を自己の
秘密鍵ｄで暗号化し、暗号化認証子ｈ（Ｃ）を得る。次
いで、暗号化認証子ｈ（Ｃ）と認証文Ｍの組を送信者か
ら受信者に送る。
【００１５】
【数６】 ｈ（Ｃ）≡（ｈ（Ｍ））d （ mod Ｎ） …（８） 受信者は、暗号化認証子ｈ（Ｃ）と認証文Ｍの組を受信
すると、送信者の公開鍵ｅを使用して、暗号化認証子ｈ
（Ｃ）を復号化し認証子ｈ（Ｍ）を得る。
【００１６】
【数７】 ｈ（Ｍ）≡（ｈ（Ｃ））e （ mod Ｎ） …（９） 次いで、受信した認証文Ｍをハッシュ関数ｈによりハッ
シュ化し、認証子ｈ（Ｍ）°を得る。そして復号化した
認証子ｈ（Ｍ）とハッシュ化した認証子ｈ（Ｍ）°とを
比較して正当性を判断する。すなわち、両者が一致して
いれば認証文が正当であり、不一致であれば不当と判断
する。
【００１７】このように、ＲＳＡ型の公開鍵暗号装置
は、公開鍵と秘密鍵の演算を逆に適用することにより、
認証通信装置としても使用することができる。
【００１８】なお、この認証通信において、前記暗号化
認証子ｈ（Ｃ）と認証文Ｍの組をさらに受信者の公開鍵
を用いて暗号化する暗号化認証通信も、認証通信と暗号
化通信とを組み合わせることによって可能であることは
いうまでもない。
【００１９】〔ラビン暗号の基本原理〕ラビン暗号にお
ける暗号化鍵は（ｂ，Ｎ）の組であり、復号化鍵は、
（ｂ，ｐ，ｑ）である。但し、ｂとＮは公開鍵であり、
ｐとｑは秘密鍵である（Ｎ＝ｐｑ）。平文をＭ、暗号文
をＣとすると、暗号化Ｅのアルゴリズムは、
【数８】 Ｃ＝Ｅ（Ｍ）＝Ｍ（Ｍ＋ｂ）（ mod Ｎ） …（１０） 式（１０）で表される。
【００２０】復号化Ｄのアルゴリズムは、
【数９】 Ｍ2 ＋Ｍｂ−Ｃ≡０ （ mod Ｎ） …（１１） 式（１１）をＭについて解くことに対応する。ところ
で、Ｎは２つの大きな素数ｐとｑの積、すなわち、
【数１０】 Ｎ＝ｐｑ …（１２） なので、式（１１）は、次の連立合同式と同値である。
【００２１】
【数１１】 Ｍ2 ＋Ｍｂ−Ｃ≡０ （ mod ｐ） …（１３） Ｍ2 ＋Ｍｂ−Ｃ≡０ （ mod ｑ） …（１４） つまり、ラビン暗号の復号化は、秘密鍵ｐとｑを知って
いる者だけが実行できる。また、ラビン暗号の安全性
は、Ｎの素因数分解の困難さを根拠としている。
【００２２】復号化Ｄは、式（１３）と（１４）を同時
に満たすＭを求めることになり、
【数１２】 Ｍ＝Ｄ(Ｃ)＝−ｂ／２±√((ｂ／２)2＋Ｃ) （ mod ｐ） …（１５） Ｍ＝Ｄ(Ｃ)＝−ｂ／２±√((ｂ／２)2＋Ｃ) （ mod ｑ） …（１６） と表すことができる。ここで、式（１５）のｂ／２（ m
od ｐ）は、２ｓ≡ｂ（mod ｐ）を満たす整数ｓを表
す。２とｐは互いに素であるので、ｓは常にただ一つ求
まる。
【００２３】また、式（１５）の√((ｂ／２)2＋Ｃ)（
mod ｐ）は、ｔ2≡(ｂ／２)2＋Ｃ（ mod ｐ）を満た
す非負整数ｔを表す。もしｔが存在するとして、ｐを４
α＋３（α：整数）の形の素数とすると、(ｂ／２)2＋
Ｃが mod ｐに関して平方剰余になり、次の式（１７）
でｔが容易に求まる。
【００２４】
【数１３】 ｔ＝((ｂ／２)2＋Ｃ)α+1 （ mod ｐ） …（１７） 式（１６）に関しても式（１５）と同様に求まる。
【００２５】ラビン暗号の暗号化関数Ｅの定義域は、式
（１０）から明らかなように、［０，Ｎ−１］の全ての
整数なので、全ての平文を暗号化できる。また、暗号化
関数Ｅは一価関数なので、ある平文Ｍ0 に対する暗号文
Ｃ0 は唯一に定まる。ところが、復号化関数Ｄは多価関
数なので、Ｍ0 に対するＣ0 を復号化しても、もとのＭ
0 が唯一に定まるとは限らない。
【００２６】この対策として、もとの平文Ｍ0 の中に意
味のある付属情報（例えば、送信者ＩＤ、受信者ＩＤ、
日付等）を含めておく。そして、受信者は復元メッセー
ジＭi （１≦ｉ≦４）の中から、この付属情報を含んで
いるメッセージを真の平文として決定する。
【００２７】〔ラビン暗号の鍵生成〕ラビン暗号の鍵生
成は、上記ＲＳＡ暗号の鍵生成の第１段階のみと同様で
あり、任意の相異なる二つの大きな素数ｐ，ｑを選び、
その積Ｎ＝ｐｑを計算する。また、０≦ｂ＜Ｎなるｂを
定める。ｐとｑとを秘密鍵とし、Ｎとｂとを公開鍵とす
る。
【００２８】〔ラビン暗号による認証〕ラビン暗号の復
号化関数Ｄは、［０，Ｎ−１］の範囲の一部の整数を定
義域にもつ。すなわち、ラビン暗号では、任意の平文Ｍ
（０≦Ｍ≦Ｎ−１）に対して、必ずしも認証通信ができ
るとは限らない。認証通信が可能となる条件は、式（１
５）、（１６）の演算が定義できることであり、具体的
には、（ｂ／２）2＋Ｍが mod ｐと mod ｑに関して平
方剰余となることである。
【００２９】これを、平方剰余記号（ルジャンドルの記
号とも呼ばれる）を用いて示せば、
【数１４】 （((ｂ／２)2＋Ｍ)／ｐ）2 ≡１ …（１８） （((ｂ／２)2＋Ｍ)／ｑ）2 ≡１ …（１９） が成立することである。
【００３０】認証通信可能なある平文Ｍ0 に署名変換Ｄ
を施すと、それぞれほぼ１／４の確率で４通りの署名文
Ｓ1,Ｓ2,Ｓ3,Ｓ4 が得られる。これらのうちのいずれの
署名文に復元処理を施しても、もとの平文Ｍ0 が復元で
きるので、いずれか１種類の署名文のみを通信すればよ
い。
【００３１】次に、任意の平文Ｍ（０≦Ｍ≦Ｎ−１）に
対してディジタル署名を可能とするための対策を説明す
る。そのためには、まず平文Ｍにある種の変換ｆj を施
す必要がある。すなわち、
【数１５】 Ｍj ＝ｆj（Ｍ） ｊ＝０，１，２，… …（２０） とする。但し、ｆ0 は無変換とする。ｆj の具体的な関
数としては、例えば、
【数１６】 ｆj（Ｍ）＝ Ｍ＋ｊ …（２１） でもよい。対策の手順は以下の通りである。
【００３２】まず、送信者は、ｊ＝０として、Ｍj が式
（１８）と（１９）とを満たすか否かをチェックする。
もし満たさなければｊ＝ｊ＋１として、再度Ｍｊが条件
を満たすか否かをチェックする。この試行は、式（２
２）に示すように、
【数１７】 平均４回のチェックで条件を満たす変換が求まり、それ
をｆj*とし、変換後の平文をＭj*とする。
【００３３】次いで、送信者は署名文Ｓ（＝Ｄ（Ｍj
*））に、ｆj*を付加して受信者に送信する。受信者は
Ｓから公開鍵を用いてＭj*を復元し、更に、Ｍj*にｆj*
の逆関数ｆj*-1を施してＭを得る。もしＭが意味のある
情報ならば、送信者の身元が認証できる。
【００３４】なお、ラビン型暗号による認証通信におい
ても、ＲＳＡ型と同様に、認証文をハッシュ化した認証
子ｈ（Ｍ）を自己の秘密鍵で暗号化した暗号化認証子ｈ
（Ｃ）と認証文Ｍの組を送信者から受信者に送り、受信
者は復号化した認証子ｈ（Ｍ）と平文Ｍをハッシュ化し
た認証子ｈ（Ｍ）°とを比較して正当性を判断してもよ
い。
【００３５】このように、ラビン型の公開鍵暗号装置
は、公開鍵と秘密鍵の演算を逆に適用することにより、
認証通信装置としても使用することができる。
【００３６】ところで、一般に暗号技術の性能評価の尺
度は、暗号を解読しようとする攻撃に対する安全性の強
度と、暗号化・復号化の速度である。強度が高く、速度
の速い暗号が優秀な暗号である。
【００３７】ＲＳＡ暗号、ラビン暗号などの公開鍵暗号
は、暗号化鍵である公開された公開鍵から、復号化鍵で
ある秘密鍵を得ることが計算量的に困難であることに安
全性の根拠を置いている。
【００３８】ＲＳＡ暗号では、公開鍵が素因数分解でき
れば、暗号文から平文を得ることができることが、文献
２：「R.L.Rivest, A.Shamir and L.Adleman; “A meth
od for obtaining digital signatures and public-key
cryptosystems．”，Comm.,ACM, vol.21, No.2, pp.12
0-126, (1978) 」に示されている。
【００３９】このように、ＲＳＡ暗号などの公開鍵暗号
は、公開情報である公開鍵から秘密鍵を得ることが計算
量的に困難であることに安全性の根拠を置いている。公
開鍵のサイズを大きく取ればそれだけ、安全性が増す。
【００４０】また、このＲＳＡ暗号は高次の冪乗計算を
行うため、計算量が多く暗号化・復号化に時間がかかる
ことが大きな欠点であった。
【００４１】冪乗計算の計算量を減らすことにより、暗
号化・復号化を高速にできるが、それには、公開鍵のサ
イズを小さくするしかなく、暗号強度の低下につながる
ことになる。
【００４２】たとえば、公開鍵ｅである暗号のべき指数
が小さい場合、文献３：「J.Hastad,“Solving simulta
neouus modular equations of low degree",SIMA Jour
malof Computing, 17,(1988), pp.336-341.」、文献４：
「D.Coppersmith, M.Franklin, J.Patarin and M.Reit
er,“Low-exponent RSA with related messages",Adva
nces in Cryptology - EUROCRYPT '96, LNCS 1070,(199
6), pp.1-9.」、文献５：「D.Coppersmith,“Finding a
small root of a univariate modular equation",Advan
ces in Cryptology- EUROCRYPT '96, LNCS 1070, (199
6), pp.155-165.」に示されていたように、ＲＳＡ暗号
は簡単に解読されるという欠点が報告された。このこと
は、実用面では、同じ平文を複数の通信相手に送る場合
（同報通信）、２個の平文に多項式関係がある場合、平
文のビット数が小さい場合などにあたる。
【００４３】ラビン暗号では、暗号文のみから元の平文
を求めることが、公開鍵を素因数分解できることと計算
量的に同値であることが、文献６：「M.O.Rabin;“Digi
talSignaturesand Public-Key Encryptions as Intract
able as Factorization",MIT,Technical Report,MIT/LC
S/TR-212(1979)」に示されている。
【００４４】また、ラビン暗号を２次元に拡張した暗号
が、文献７：「小林、田村、根本；“２次元の変形ラビ
ン暗号”、電子情報通信学会論文誌、J72-A,5,(1989)」
や文献８：「K.Koyama; “Security and Unique Deciph
erability of Twodimensional Public Key Cryptosyste
ms”,IEICE Transcations,v.E73,n.7,pp.1057-1067,(19
90) 」などに示されている。
【００４５】ラビン暗号の特徴は、暗号化が高速である
点にある。ただし、ラビン暗号も従来の公開鍵暗号は、
公開鍵を超えるデータ長の平文を暗号通信する場合、公
開鍵の長さのブロック毎（２次元の場合は公開鍵の２
倍）に個別に暗号化する必要があった。つまり、公開鍵
の長さが暗号通信の単位になっていた。
【００４６】また、ラビン暗号は部分解読に対して大変
に弱いという欠点があった。例えば、前記文献３、文献
４、および文献５に示されていたように、同報通信の場
合、２個の平文に多項式関係がある場合、平文のビット
数が小さい場合など、簡単に解読可能であるという欠点
がある。
【００４７】
【発明が解決しようとする課題】このように従来の公開
鍵暗号は、安全性を高めようとすれば、鍵のサイズを大
きくする必要があり、鍵を大きくすると、暗号化及び復
号化の速度が低下するという、安全性と速度とが両立し
ないという問題点があった。
【００４８】以上の問題点に鑑み、本発明の課題は、従
来のＲＳＡ暗号やラビン暗号と比較して、同程度の強度
を持ちながら、復号化速度を大幅に向上させた暗号通信
方法および同方法を実現する装置を提供することであ
る。
【００４９】また、本発明の別の課題は、認証装置とし
ても利用可能であり、ひとつの装置で暗号化通信と認証
の両用が可能となるような暗号化通信方法および認証方
法およびこれらを実現する装置を提供することである。
【００５０】さらに、本発明の別の課題は、同報通信の
場合、２個の平文に多項式関係がある場合、平文のビッ
ト数が小さい場合などに、暗号強度が著しく低下すると
いう従来のＲＳＡ暗号およびラビン暗号の欠陥を克服し
た暗号通信方法および同方法を実現する装置を提供する
ことである。
【００５１】
【課題を解決するための手段】上記課題を解決するた
め、本発明は次の構成を有する。すなわち、請求項１記
載の発明は、暗号化の対象である平文データと、それぞ
れｐとｑとを値とする２つの素数データで構成される第
１の秘密鍵データと、ｄを値とする第２の秘密鍵データ
と、ｐとｑとの積Ｎを値とする第１の公開鍵データと、
ｅを値とする第２の公開鍵データと、２以上の整数であ
るｋを値とするブロック数データと、を用いる公開鍵型
のＮ進表現暗号による通信方法であって、前記Ｎを基数
とするＮ進位取り記数法により前記平文データをｋ桁の
Ｎ進数データとして表現する第１の過程と、前記ｋ桁の
Ｎ進数データに対して、第１及び第２の公開鍵データを
使用する演算により、前記平文データを暗号化した暗号
文データを得る第２の過程と、第１の公開鍵データ及び
第２の秘密鍵データを用いて、前記暗号文データから前
記Ｎ進数の最下位桁の値を復号化する第３の過程と、前
記復号化された最下位桁の値を用いて、前記Ｎ進数の上
位の桁の値を順次復号化する第４の過程と、前記復号化
されたＮ進数の各桁の値を用いて前記平文データを復元
する第５の過程と、を備えたことを要旨とするＮ進表現
暗号による通信方法である。
【００５２】また、請求項２記載の発明は、請求項１に
記載のＮ進表現暗号による通信方法において、前記第１
の過程は、前記平文データの先頭に予め第１の公開鍵デ
ータＮのビット長程度の乱数を連接して連接データを作
成し、以下この連接データを平文データとして、前記Ｎ
を基数とするＮ進位取り記数法によりｋ桁のＮ進数デー
タとして表現する過程であることを要旨とする。
【００５３】また、請求項３記載の発明は、暗号化の対
象である平文データと、それぞれｐとｑとを値とする２
つの素数データの積Ｎを値とする第１の公開鍵データ
と、ｅを値とする第２の公開鍵データと、２以上の整数
であるｋを値とするブロック数データと、を用いて、前
記平文データに該当する暗号文データを生成する公開鍵
型のＮ進表現暗号による暗号化方法であって、各ブロッ
クがＮの剰余類の範囲に収まるように、前記平文データ
を複数のブロックに分割するとともに、分割されたブロ
ックの数ｋを計数する第１の過程と、前記分割された各
ブロックのデータを、それぞれＮ進数の形態で表現する
第２の過程と、前記平文データの全体が、ｋ桁のＮ進数
として位取りされるように各ブロックのデータを順次結
合する第３の過程と、Ｎのｋ乗を法として、前記結合さ
れたデータをｅ乗した値である暗号文データを計算する
第４の過程と、を備えたことを要旨とするＮ進表現暗号
による暗号化方法である。
【００５４】また、請求項４記載の発明は、暗号化の対
象である平文データと、それぞれｐとｑとを値とする２
つの素数データの積Ｎを値とする第１の公開鍵データ
と、ｅを値とする第２の公開鍵データと、２以上の整数
であるｋを値とするブロック数データと、を用いて、前
記平文データに該当する暗号文データを生成する公開鍵
型のＮ進表現暗号による暗号化プログラムを格納した記
憶媒体であって、各ブロックがＮの剰余類の範囲に収ま
るように、前記平文データを複数のブロックに分割する
とともに、分割されたブロックの数ｋを計数し、前記分
割された各ブロックのデータを、それぞれＮ進数の形態
で表現し、前記平文データの全体が、ｋ桁のＮ進数とし
て位取りされるように各ブロックのデータを順次結合
し、Ｎのｋ乗を法として、前記結合されたデータをｅ乗
した値である暗号文データを計算すること、を要旨とす
るＮ進表現暗号による暗号化プログラムを格納した記憶
媒体である。
【００５５】また、請求項５記載の発明は、暗号化の対
象である平文データと、それぞれｐとｑとを値とする２
つの素数データの積Ｎを値とする第１の公開鍵データ
と、ｅを値とする第２の公開鍵データと、２以上の整数
であるｋを値とするブロック数データと、を用いて、前
記平文データに該当する暗号文データを生成する公開鍵
型のＮ進表現暗号による暗号化装置であって、各ブロッ
クがＮの剰余類の範囲に収まるように、前記平文データ
を複数のブロックに分割するとともに、分割されたブロ
ックの数ｋを計数する平文分割手段と、前記平文分割手
段が分割した各ブロックのデータを順次格納する記憶手
段と、前記記憶された各ブロックのデータが１つのＮ進
数の各桁の値を示すように、各ブロックのデータを順次
結合した結合データを生成するデータ結合手段と、Ｎの
ｋ乗を法として、前記結合データをｅ乗した値である暗
号文データを生成する暗号化手段と、を備えたことを要
旨とするＮ進表現暗号による暗号化装置である。
【００５６】また、請求項６記載の発明は、平文データ
からＮ進表現暗号により暗号化された暗号文データと、
それぞれｐとｑとを値とする２つの素数データの積Ｎを
値とする第１の公開鍵データと、ｅを値とする第２の公
開鍵データと、ｄを値とする第２の秘密鍵データと、２
以上の整数であるｋを値とするブロック数データと、を
用いて、前記暗号文データに該当する平文データを復元
する公開鍵型のＮ進表現暗号の復号化方法であって、Ｎ
を法として前記暗号文データの値をｄ乗することによっ
て、前記平文データをＮ進位取り記数法で表現したとき
の最下位桁の値Ｍ0 を求める第１の過程と、このＭ0 に
基づいて、１次合同式を用いて、自然数の中から、その
値をｅ乗した値に対して、Ｎのｋ乗を法とする剰余が前
記暗号文データの値に等しくなるような自然数を、Ｍ0
を最下位桁とし桁数がｋであるＮ進数表現の形で求める
第２の過程（以下、この過程を上位桁復号化過程と称す
る）と、これらのＮ進数の各桁の数値を順次連結するこ
とによって平文データを生成する第３の過程と、を備え
たことを要旨とするＮ進表現暗号の復号化方法である。
【００５７】また、請求項７記載の発明は、請求項６に
記載のＮ進表現暗号の復号化方法において、前記上位桁
復号化過程は、前記Ｍ0 を最下位桁の値とし桁数がｋで
あるＮ進数として複数の平文ブロックを表現したもの全
体をｅ乗した形である暗号文を、前記ｅ乗を展開して得
られるＮに関するｋ−１次の多項式に対応させ、該ｋ−
１次の多項式のそれぞれの係数値を、前記複数の平文ブ
ロックを変数とする多項式関数とみなして、前記暗号文
データ及び前記Ｎ進数の既に求められた下位の桁の値に
基づいて、低次の係数から高次の係数へ昇順に順次求め
る係数値計算過程と、これらの係数値を使って、Ｎを法
とする１次合同式を解くことにより、前記Ｎ進数におけ
る上位の桁の値を順次確定していく上位桁計算過程と、
を備えたことを要旨とする。
【００５８】また、請求項８記載の発明は、請求項７に
記載のＮ進表現暗号の復号化方法において、前記係数値
計算過程は、求められた係数の値を係数テーブルに順次
記憶するとともに、該係数テーブルに記憶された低次の
係数の値を参照することを含むことを要旨とする。
【００５９】また、請求項９記載の発明は、請求項７に
記載のＮ進表現暗号の復号化方法において、前記ｋ桁の
Ｎ進数の各桁の値をＭi （０≦ｉ≦ｋ−１）とすると
き、前記上位桁復号化過程は、前記最下位桁の値Ｍ0
と、第１の公開鍵データＮと、第２の公開鍵データｅ
と、暗号文データＣと、ブロック数データｋとを入力と
して、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基づいてＭi を求める
同一の写像もしくは同一の計算式により、再帰的にＭ1
からＭk-1 までを順次復号化することを要旨とする。
【００６０】また、請求項１０記載の発明は、平文デー
タからＮ進表現暗号により暗号化された暗号文データ
と、それぞれｐとｑとを値とする２つの素数データの積
Ｎを値とする第１の公開鍵データと、ｅを値とする第２
の公開鍵データと、ｄを値とする第２の秘密鍵データ
と、２以上の整数であるｋを値とするブロック数データ
と、を用いて、前記暗号文データに該当する平文データ
を復元する公開鍵型のＮ進表現暗号の復号化プログラム
を格納した記憶媒体であって、Ｎを法として前記暗号文
データの値をｄ乗することによって、前記平文データを
Ｎ進位取り記数法で表現したときの最下位桁の値Ｍ0 を
求め、このＭ0 に基づいて、１次合同式を用いて、自然
数の中から、その値をｅ乗した値に対して、Ｎのｋ乗を
法とする剰余が前記暗号文データの値に等しくなるよう
な自然数を、Ｍ0 を最下位桁とし桁数がｋであるＮ進数
表現の形で求め、これらのＮ進数の各桁の数値を順次連
結することによって平文データを生成する、ことを要旨
とするＮ進表現暗号の復号化プログラムを格納した記憶
媒体である。
【００６１】また、請求項１１記載の発明は、平文デー
タからＮ進表現暗号により暗号化された暗号文データ
と、それぞれｐとｑとを値とする２つの素数データの積
Ｎを値とする第１の公開鍵データと、ｅを値とする第２
の公開鍵データと、ｄを値とする第２の秘密鍵データ
と、２以上の整数であるｋを値とするブロック数データ
と、を用いて、前記暗号文データに該当する平文データ
を復元するＮ進表現暗号の復号化装置であって、Ｎを法
として、前記暗号文データをｄ乗した値の剰余を求める
ことにより、前記平文データをＮ進位取り記数法で表現
したときの最下位桁の値Ｍ0 を得る最下位桁復号化手段
と、このＭ0 に基づいて、自然数の中から、Ｎのｋ乗を
法として、その値をｅ乗した値が前記暗号文データの値
に等しくなるような自然数を、Ｍ0 を最下位桁とし桁数
がｋであるＮ進数表現の形で求める上位桁復号化手段
と、前記Ｎ進数の各桁の数値を順次連結することによっ
て平文データを生成するデータ連結手段と、を備えてな
り、前記上位桁復号化手段は、前記Ｍ0 を最下位桁の値
とし桁数がｋであるＮ進数として複数の平文ブロックを
表現したもの全体をｅ乗した形である暗号文を、前記ｅ
乗を展開して得られるＮに関するｋ−１次の多項式に対
応させ、該ｋ−１次の多項式のそれぞれの係数値を、前
記複数の平文ブロックを変数とする多項式関数とみなし
て、前記暗号文データ及び前記Ｎ進数の既に求められた
下位の桁の値に基づいて、低次の係数から高次の係数へ
昇順に順次求める係数値計算手段と、この係数計算手段
により求められた係数値を使って、Ｎを法とする１次合
同式を解くことにより、前記Ｎ進数における上位の桁の
値を順次確定していく上位桁計算手段と、を備えたこと
を要旨とするＮ進表現暗号の復号化装置である。
【００６２】また、請求項１２記載の発明は、請求項１
１に記載のＮ進表現暗号の復号化装置において、前記係
数計算手段は、既に求められた低次の係数の値を順次記
憶した係数テーブル記憶手段と、この係数テーブル記憶
手段から求めるべき係数より低次の係数値を読み出す読
出し手段と、を備えたことを要旨とする。
【００６３】また、請求項１３記載の発明は、平文デー
タＭからＮ進表現暗号により暗号化された暗号文データ
Ｃと、それぞれｐとｑとを値とする２つの素数データの
積Ｎを値とする第１の公開鍵データと、ｅを値とする第
２の公開鍵データと、ｄを値とする第２の秘密鍵データ
と、２以上の整数であるｋを値とするブロック数データ
と、を用いて、前記暗号文データＣに該当する平文デー
タＭを復元するＮ進表現暗号の復号化装置であって、Ｎ
を法として、前記暗号文データをｄ乗した値の剰余を求
めることにより、前記平文データをＮ進位取り記数法で
表現したときの最下位桁の値Ｍ0 を得る最下位桁復号化
手段と、前記最下位桁の値Ｍ0 と、第１の公開鍵データ
Ｎと、第２の公開鍵データｅと、暗号文データＣと、ブ
ロック数データｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍ
i-1 に基づいてＭi （１≦ｉ≦ｋ−１）を求める同一の
写像もしくは同一の計算式により、再帰的に前記Ｎ進数
表現の上位桁であるＭ1 からＭk-1 までを順次復号化す
る上位桁復号化手段と、前記Ｎ進数の各桁の数値を順次
連結することによって平文データを生成するデータ連結
手段と、を備えたことを要旨とするＮ進表現暗号の復号
化装置である。
【００６４】また、請求項１４記載の発明は、認証対象
である認証文データＭと、それぞれｐとｑとを値とする
２つの素数データで構成される第１の秘密鍵データと、
ｄを値とする第２の秘密鍵データと、ｐとｑとの積Ｎを
値とする第１の公開鍵データと、ｅを値とする第２の公
開鍵データと、２以上の整数であるｋを値とするブロッ
ク数データと、を用いる公開鍵型のＮ進表現暗号による
認証方法であって、前記認証文データに基づいて認証子
データｈ(Ｍ)を生成する第１の過程と、第１の公開鍵デ
ータ及び第２の秘密鍵データを用いる演算により、前記
認証子データｈ(Ｍ)からＮ進数表現された暗号化認証子
データｈ(Ｃ)の最下位桁の値ｈ(Ｃ)0 を生成する第２の
過程と、前記生成された最下位桁の値ｈ(Ｃ)0 を用い
て、前記Ｎ進数表現された暗号化認証子データの上位の
桁の値を順次生成する第３の過程と、前記生成されたＮ
進数の各桁の値を示すブロックを順次連結して暗号化認
証子データｈ(Ｃ)を生成する第４の過程と、前記暗号化
認証子データｈ(Ｃ)と前記Ｎ進数の桁数ｋと認証文デー
タＭとを認証相手に送信する第５の過程と、前記暗号化
認証子データ全体を１つのｋ桁のＮ進数として、これに
対して、第１及び第２の公開鍵データを使用する演算に
より、前記暗号化認証子データｈ(Ｃ)から復号化された
認証子データｈ(Ｍ)を得る第６の過程と、前記復号化さ
れた認証子データｈ(Ｍ)と前記認証文データＭとを用い
て認証を行う第７の過程と、を備えたこと要旨とするＮ
進表現暗号による認証方法である。
【００６５】また、請求項１５記載の発明は、認証対象
となる認証子データｈ(Ｍ)と、それぞれｐとｑとを値と
する２つの素数データの積Ｎを値とする第１の公開鍵デ
ータと、ｄを値とする第２の秘密鍵データと、２以上の
整数であるｋを値とするブロック数データと、を用い
て、前記認証子データｈ(Ｍ)を暗号化した暗号化認証子
データｈ(Ｃ)を生成するＮ進表現暗号による認証文生成
方法であって、Ｎを法として前記認証子データの値をｄ
乗した値を計算し、この値を前記認証子データｈ(Ｍ)を
暗号化してＮ進表現したときの最下位桁の値ｈ(Ｃ)0 と
する第１の過程と、このｈ(Ｃ)0 に基づいて、自然数の
中から、Ｎのｋ乗を法としてその値をｄ乗した値が前記
認証子データｈ(Ｍ)の値に等しくなるような自然数を、
ｈ(Ｃ)0 を最下位桁の値としたｋ桁のＮ進数として表現
した形で求める第２の過程（以下、この過程を認証子上
位桁暗号化過程と称する）と、このＮ進数の各桁を表わ
す数値データを順次連結することによって、暗号化認証
子データｈ(Ｃ)を生成する第３の過程と、を備えたこと
を要旨とするＮ進表現暗号による認証文生成方法であ
る。
【００６６】また、請求項１６記載の発明は、請求項１
５に記載のＮ進表現暗号による認証文生成方法におい
て、前記認証子上位桁暗号化過程は、前記ｈ(Ｃ)0 を最
下位桁の値とし桁数がｋであるＮ進数として前記認証子
データｈ(Ｍ)を表現したもの全体をｄ乗した形である暗
号化認証子データｈ(Ｃ)を、前記ｄ乗を展開して得られ
るＮに関するｋ−１次の多項式に対応させ、該ｋ−１次
の多項式のそれぞれの係数値を、前記認証子データを変
数とする多項式関数とみなして、前記認証子データｈ
(Ｍ)及び前記Ｎ進数の既に求められた下位の桁の値に基
づいて、低次の係数から高次の係数へ昇順に順次求める
係数値計算過程と、これらの係数値を使って、Ｎを法と
する１次合同式を解くことにより、前記Ｎ進数における
上位の桁の値を順次確定していく上位桁計算過程と、を
備えたことを要旨とする。
【００６７】また、請求項１７記載の発明は、請求項１
６に記載のＮ進表現暗号による認証文生成方法におい
て、前記係数値計算過程は、求められた係数の値を係数
テーブルに順次記憶するとともに、該係数テーブルに記
憶された低次の係数の値を参照することを含むことを要
旨とする。
【００６８】また、請求項１８記載の発明は、請求項１
５に記載のＮ進表現暗号による認証文生成方法におい
て、前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i （０≦ｉ≦
ｋ−１）とするとき、前記認証子上位桁暗号化過程は、
前記最下位桁の値ｈ(Ｃ)0 と、第１の公開鍵データＮ
と、第２の公開鍵データｅと、認証子データｈ(Ｍ)と、
ブロック数データｋとを入力として、ｈ(Ｃ)0 ，ｈ(Ｃ)
1 ，…，ｈ(Ｃ)i-1 に基づいてｈ(Ｃ)i を求める同一の
写像もしくは同一の計算式により、再帰的にｈ(Ｃ)1 か
らｈ(Ｃ)k-1 までを順次暗号化することを要旨とする。
【００６９】また、請求項１９記載の発明は、認証対象
となる認証子データｈ(Ｍ)と、それぞれｐとｑとを値と
する２つの素数データの積Ｎを値とする第１の公開鍵デ
ータと、ｄを値とする第２の秘密鍵データと、２以上の
整数であるｋを値とするブロック数データと、を用い
て、前記認証子データｈ(Ｍ)を暗号化した暗号化認証子
データｈ(Ｃ)を生成するＮ進表現暗号による認証文生成
プログラムを格納した記憶媒体であって、Ｎを法として
前記認証子データの値をｄ乗した値を計算し、この値を
前記認証子データｈ(Ｍ)を暗号化してＮ進表現したとき
の最下位桁の値ｈ(Ｃ)0 とし、このｈ(Ｃ)0 に基づい
て、自然数の中から、Ｎのｋ乗を法としてその値をｄ乗
した値が前記認証子データｈ(Ｍ)の値に等しくなるよう
な自然数を、ｈ(Ｃ)0 を最下位桁の値としたｋ桁のＮ進
数として表現した形で求め、このＮ進数の各桁を表わす
数値データを順次連結することによって、暗号化認証子
データｈ(Ｃ)を生成する、ことを要旨とするＮ進表現暗
号による認証文生成プログラムを格納した記憶媒体であ
る。
【００７０】また、請求項２０記載の発明は、認証対象
となる認証子データｈ(Ｍ)と、それぞれｐとｑとを値と
する２つの素数データの積Ｎを値とする第１の公開鍵デ
ータと、ｄを値とする第２の秘密鍵データと、２以上の
整数であるｋを値とするブロック数データと、を用い
て、前記認証子データｈ(Ｍ)を暗号化した暗号化認証子
データｈ(Ｃ)を生成するＮ進表現暗号による認証文生成
装置であって、Ｎを法として、前記認証子データの値を
ｄ乗した値ｈ(Ｃ)0 を計算する最下位桁計算手段と、ｈ
(Ｃ)0 に基づいて、自然数の中から、Ｎのｋ乗を法とし
てその値をｄ乗した値が、前記認証子データの値に等し
くなるような自然数を、ｈ(Ｃ)0 を最下位桁の値とした
ｋ桁のＮ進数として表現した形で求める認証子上位桁暗
号化手段と、このＮ進数の各桁を表わす数値データを順
次連結することによって、暗号化認証子データｈ(Ｃ)を
生成する連結手段と、を備えてなり、前記認証子上位桁
暗号化手段は、前記ｈ(Ｃ)0 を最下位桁の値とし桁数が
ｋであるＮ進数として前記認証子データｈ（Ｍ）を表現
したもの全体をｄ乗した形である暗号化認証子データｈ
（Ｃ）を、前記ｄ乗を展開して得られるＮに関するｋ−
１次の多項式に対応させ、該ｋ−１次の多項式のそれぞ
れの係数値を、前記認証子データを変数とする多項式関
数とみなして、前記認証子データｈ(Ｍ)及び前記Ｎ進数
の既に求められた下位の桁の値に基づいて、低次の係数
から高次の係数へ昇順に順次求める係数計算手段と、こ
れらの係数値を使って、Ｎを法とする１次合同式を解く
ことにより、前記Ｎ進数におけるより上位の桁の値を順
次確定していく上位桁計算手段と、を備えたことを要旨
とするＮ進表現暗号による認証文生成装置である。
【００７１】また、請求項２１記載の発明は、請求項２
０に記載のＮ進表現暗号による認証文生成装置におい
て、前記係数計算手段は、既に求められた低次の係数の
値を順次記憶した係数テーブル記憶手段と、この係数テ
ーブル記憶手段から求めるべき係数より低次の係数値を
読み出す読出し手段と、を備えたことを要旨とする。
【００７２】また、請求項２２記載の発明は、認証対象
となる認証子データｈ(Ｍ)と、それぞれｐとｑとを値と
する２つの素数データの積Ｎを値とする第１の公開鍵デ
ータと、ｅを値とする第２の公開鍵データと、ｄを値と
する第２の秘密鍵データと、２以上の整数であるｋを値
とするブロック数データと、を用いて、前記認証子デー
タｈ(Ｍ)を暗号化した暗号化認証子データｈ(Ｃ)を生成
するＮ進表現暗号による認証文生成装置であって、Ｎを
法として、前記認証子データの値をｄ乗した値ｈ(Ｃ)0
を計算する最下位桁計算手段と、ｈ(Ｃ)0 に基づいて、
自然数の中から、Ｎのｋ乗を法としてその値をｄ乗した
値が、前記認証子データの値に等しくなるような自然数
を、ｈ(Ｃ)0 を最下位桁の値としたｋ桁のＮ進数として
表現した形で求める認証子上位桁暗号化手段と、このＮ
進数の各桁を表わす数値データを順次連結することによ
って、暗号化認証子データｈ(Ｃ)を生成する連結手段
と、を備えてなり、前記ｋ桁のＮ進数の各桁の値をｈ
(Ｃ)i （０≦ｉ≦ｋ−１）とするとき、前記認証子上位
桁暗号化手段は、前記最下位桁の値ｈ(Ｃ)0 と、第１の
公開鍵データＮと、第２の公開鍵データｅと、認証子デ
ータｈ(Ｍ)と、ブロック数データｋとを入力として、ｈ
(Ｃ)0 ，ｈ(Ｃ)1 ，…，ｈ(Ｃ)i-1 に基づいてｈ(Ｃ)i
を求める同一の写像もしくは同一の計算式により、再帰
的にｈ(Ｃ)1 からｈ(Ｃ)k-1 までを順次暗号化すること
を要旨とするＮ進表現暗号による認証文生成装置であ
る。
【００７３】また、請求項２３記載の発明は、認証対象
である認証文データＭと、この認証文データから前記請
求項１５、１６、１７、１８、２０、２１、２２のいず
れか一項に記載の方法または装置により生成された暗号
化認証子データｈ(Ｃ)と、この暗号化認証子データｈ
(Ｃ)のブロック数ｋを値とするブロック数データと、そ
れぞれｐとｑとを値とする２つの素数データの積Ｎを値
とする第１の公開鍵データと、ｅを値とする第２の公開
鍵データと、を用いて、前記認証文データＭ及びまたは
前記暗号化認証子データｈ(Ｃ)が正当であるか否かを判
別する認証文検証方法であって、前記暗号化認証子デー
タｈ(Ｃ)の各ブロックをｋ桁のＮ進数の各桁として順次
結合する第１の過程と、Ｎのｋ乗を法として、この結合
されたデータをｅ乗した値である復号化された認証子デ
ータｈ(Ｍ)を求める第２の過程と、この復号化された認
証子データｈ(Ｍ)と前記認証文データＭに基づいて生成
された認証子データｈ(Ｍ)′とを比較し、この両者が一
致していた場合は、一連の認証ないし検証過程が正常で
あったと判定し、この両者が不一致であった場合は、一
連の認証ないし検証過程のいずれかに異常があったと判
定する第３の過程と、を備えたことを要旨とするＮ進表
現暗号による認証文検証方法である。
【００７４】また、請求項２４記載の発明は、認証対象
である認証文データＭと、この認証文データから前記請
求項１５、１６、１７、１８、２０、２１、２２のいず
れか一項に記載の方法または装置により生成された暗号
化認証子データｈ(Ｃ)と、この暗号化認証子データｈ
(Ｃ)のブロック数ｋを値とするブロック数データと、そ
れぞれｐとｑとを値とする２つの素数データの積Ｎを値
とする第１の公開鍵データと、ｅを値とする第２の公開
鍵データと、を用いて、前記認証文データＭ及びまたは
前記暗号化認証子データｈ(Ｃ)が正当であるか否かを判
別する認証文検証プログラムを格納した記憶媒体であっ
て、前記暗号化認証子データｈ(Ｃ)の各ブロックをｋ桁
のＮ進数の各桁として順次結合し、Ｎのｋ乗を法とし
て、この結合されたデータをｅ乗した値である復号化さ
れた認証子データｈ(Ｍ)を求め、この復号化された認証
子データｈ(Ｍ)と前記認証文データＭに基づいて生成さ
れた認証子データｈ(Ｍ)′とを比較し、この両者が一致
していた場合は、一連の認証ないし検証過程が正常であ
ったと判定し、この両者が不一致であった場合は、一連
の認証ないし検証過程のいずれかに異常があったと判定
する、ことを要旨とするＮ進表現暗号による認証文検証
プログラムを格納した記憶媒体である。
【００７５】また、請求項２５記載の発明は、認証対象
である認証文データＭと、この認証文データＭから前記
請求項１５、１６、１７、１８、２０、２１、２２のい
ずれか一項に記載の方法または装置により生成された暗
号化認証子データｈ(Ｃ)と、この暗号化認証子データｈ
(Ｃ)のブロック数ｋを値とするブロック数データと、そ
れぞれｐとｑとを値とする２つの素数データの積Ｎを値
とする第１の公開鍵データと、ｅを値とする第２の公開
鍵データと、を用いて、前記認証文データＭ及びまたは
前記暗号化認証子データｈ(Ｃ)が正当であるか否かを判
別する認証文検証装置であって、前記認証文データＭを
ハッシュ化し、ハッシュ化認証子データｈ(Ｍ)′を生成
するハッシュ化手段と、前記暗号化認証子データｈ(Ｃ)
の各ブロックをｋ桁のＮ進数の各桁として順次結合する
結合手段と、Ｎのｋ乗を法として、この結合されたデー
タをｅ乗した値を求めて復号化された復号化認証子デー
タｈ(Ｍ)を得る認証子復号化手段と、前記復号化認証子
データｈ(Ｍ)と前記ハッシュ化認証子データｈ(Ｍ)′と
を比較し、この両者が一致していた場合は、一連の認証
ないし検証過程が正常であったと判定し、この両者が不
一致であった場合は、一連の認証ないし検証過程のいず
れかに異常があったと判定する照合判定手段と、を備え
たことを要旨とするＮ進表現暗号による認証文検証装置
である。
【００７６】また、請求項２６記載の発明は、暗号化の
対象である平文データと、それぞれｐとｑとを値とする
２つの素数データで構成される秘密鍵データと、ｐとｑ
との積Ｎを値とする公開鍵データと、２以上の整数であ
るｋを値とするブロック数データと、を用いた公開鍵型
のＮ進表現暗号による通信および認証方法であって、前
記平文データを、Ｎの剰余類の範囲でｋ個のブロックに
分割する第１の過程と、前記分割された各ブロックの値
をＮ進数の各桁の値とするとともに、Ｎを基数とするＮ
進位取り記数法により前記平文データをｋ桁のＮ進数と
して表現する第２の過程と、前記ブロック数ｋを第２の
公開鍵データとし、前記ｋ桁のＮ進数に対して、公開鍵
データを用いる演算により、前記平文データに該当する
暗号文データを得る第３の過程と、前記秘密鍵データ
と、前記公開鍵データとを用いて、前記暗号文データか
ら前記ｋ桁のＮ進数の最下位桁の値を復号化する第４の
過程と、前記復号化された最下位桁の値を用いて、前記
ｋ桁のＮ進数の上位の桁の値を順次復号化する第５の過
程と、を備えたことを要旨とするＮ進表現暗号による通
信方法である。
【００７７】また、請求項２７記載の発明は、請求項２
６に記載のＮ進表現暗号による通信方法において、前記
第１の過程は、前記平文データの先頭に予め第１の公開
鍵データＮのビット長程度の乱数を連接して連接データ
を作成し、以下この連接データを平文データとして、前
記Ｎを基数とするＮ進位取り記数法によりｋ桁のＮ進数
データとして表現する過程であることを要旨とする。
【００７８】また、請求項２８記載の発明は、暗号化の
対象である平文データＭと、それぞれｐとｑとを値とす
る２つの素数データで構成された秘密鍵データ同士の積
Ｎを値とする公開鍵データと、２以上の整数であるｋを
値とするブロック数データと、を用いて、前記平文デー
タに該当する暗号文データを生成する公開鍵型のＮ進表
現暗号による暗号化方法であって、各ブロックがＮの剰
余類の範囲に収まるように、前記平文データＭをｋ個の
ブロックに分割する第１の過程と、前記平文データＭ全
体がｋ桁のＮ進数として位取りされるように各ブロック
のデータを順次結合する第２の過程と、前記結合された
データを２乗する第３の過程と、この２乗されたデータ
に対して、Ｎをｋ乗した数値を法とした剰余である暗号
文データＣを生成する第４の過程と、を備えたことを要
旨とするＮ進表現暗号による暗号化方法である。
【００７９】また、請求項２９記載の発明は、暗号化の
対象である平文データＭと、それぞれｐとｑとを値とす
る２つの素数データで構成された秘密鍵データ同士の積
Ｎを値とする公開鍵データと、２以上の整数であるｋを
値とするブロック数データと、を用いて、前記平文デー
タに該当する暗号文データを生成する公開鍵型のＮ進表
現暗号による暗号化プログラムを格納した記憶媒体であ
って、各ブロックがＮの剰余類の範囲に収まるように、
前記平文データＭをｋ個のブロックに分割し、前記平文
データＭ全体がｋ桁のＮ進数として位取りされるように
各ブロックのデータを順次結合し、前記結合されたデー
タを２乗し、この２乗されたデータに対して、Ｎをｋ乗
した数値を法とした剰余である暗号文データＣを生成す
る、ことを要旨とするＮ進表現暗号による暗号化プログ
ラムを格納した記憶媒体である。
【００８０】また、請求項３０記載の発明は、暗号化の
対象である平文データＭと、それぞれｐとｑとを値とす
る２つの素数データで構成される秘密鍵データ同士の積
Ｎを値とする公開鍵データと、２以上の整数であるｋを
値とするブロック数データと、を用いて、前記平文デー
タに該当する暗号文データを生成するＮ進表現暗号によ
る暗号化装置であって、各ブロックがＮの剰余類の範囲
に収まるように、前記平文データＭをｋ個のブロックに
分割する平文分割手段と、前記平文データＭ全体がｋ桁
のＮ進数として位取りされるように、前記各ブロックの
データを順次結合した結合データを生成するデータ結合
手段と、Ｎをｋ乗した数値を法として、前記結合データ
を２乗することにより暗号文データＣを生成する暗号化
手段と、を備えたことを要旨とするＮ進表現暗号による
暗号化装置である。
【００８１】また、請求項３１記載の発明は、暗号化さ
れた暗号文データＣと、２以上の整数であるｋを値とす
るブロック数データと、それぞれｐとｑとを値とする２
つの素数データで構成される秘密鍵データと、ｐとｑと
の積Ｎを値とする公開鍵データと、を用いて、前記暗号
文データＣに該当する平文データＭを復元する復号化方
法であって、自然数の中から、その値を２乗した値が、
Ｎを法として暗号文データＣに等しくなるような自然数
ｘを、数値ｐを法とする剰余ならびに数値ｑを法とする
剰余を用いて求め、この値ｘを桁数がｋであるＮ進数の
最下位桁の値Ｍ0 とする第１の過程と、Ｍ0 の値と前記
暗号文データＣとを含む１次合同式を用いて、桁数がｋ
であるＮ進数の各桁の値を下位から逐次求める第２の過
程（以下、この過程を上位桁復号化過程と称する）と、
このＮ進数の各桁の数値データを順次連結し、全体とし
て１つのＮ進数データとすることによって、上記暗号文
データに該当する平文データＭを復元する第３の過程
と、を備えたことを要旨とするＮ進表現暗号による復号
化方法である。
【００８２】また、請求項３２記載の発明は、請求項３
１に記載のＮ進表現暗号の復号化方法において、前記上
位桁復号化過程は、前記Ｍ0 を最下位桁の値とし桁数が
ｋであるＮ進数として表現したデータ全体を２乗した形
である暗号文を、前記２乗を展開して得られるＮに関す
るｋ−１次の多項式に対応させ、該ｋ−１次の多項式の
それぞれの係数値を、前記複数の平文ブロックを変数と
する多項式関数とみなして、前記暗号文データ及び前記
Ｎ進数の既に求められた下位の桁の値に基づいて、この
ｋ−１次の式の係数値を昇順に順次求める過程と、求め
た係数値を使って、Ｎを法とする１次合同式を解くこと
により、前記Ｎ進数におけるより上位の桁の値を順次確
定していく過程と、を含むことを要旨とする。
【００８３】また、請求項３３記載の発明は、請求項３
１に記載のＮ進表現暗号の復号化方法において、前記ｋ
桁のＮ進数の各桁の値をＭi （０≦ｉ≦ｋ−１）とする
とき、前記上位桁復号化過程は、前記最下位桁の値Ｍ0
と、公開鍵データＮと、暗号文データＣと、ブロック数
データｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基
づいてＭi を求める同一の写像もしくは同一の計算式に
より、再帰的にＭ1 からＭk-1 までを順次復号化するこ
とを要旨とする。
【００８４】また、請求項３４記載の発明は、暗号化さ
れた暗号文データＣと、２以上の整数であるｋを値とす
るブロック数データと、それぞれｐとｑとを値とする２
つの素数データで構成される秘密鍵データと、ｐとｑと
の積Ｎを値とする公開鍵データと、を用いて、前記暗号
文データＣに該当する平文データＭを復元する復号化プ
ログラムを格納した記憶媒体であって、自然数の中か
ら、その値を２乗した値が、Ｎを法として暗号文データ
Ｃに等しくなるような自然数ｘを、数値ｐを法とする剰
余ならびに数値ｑを法とする剰余を用いて求め、この値
ｘを桁数がｋであるＮ進数の最下位桁の値Ｍ0 とし、Ｍ
0 の値と前記暗号文データＣとを含む１次合同式を用い
て、桁数がｋであるＮ進数の各桁の値を下位から逐次求
め、このＮ進数の各桁の数値データを順次連結し、全体
として１つのＮ進数データとすることによって、上記暗
号文データに該当する平文データＭを復元する、ことを
要旨とするＮ進表現暗号による復号化プログラムを格納
した記憶媒体である。
【００８５】また、請求項３５記載の発明は、暗号化さ
れた暗号文データＣと、２以上の整数であるｋを値とす
るブロック数データと、それぞれｐとｑとを値とする２
つの素数データで構成される秘密鍵データと、ｐとｑと
の積Ｎを値とする公開鍵データと、を用いて、前記暗号
文データＣに該当する平文データＭを復元する復号化装
置であって、自然数の中から、その値を２乗した値が、
Ｎを法として暗号文データＣに等しくなるような自然数
ｘを、数値ｐを法とする剰余ならびに数値ｑを法とする
剰余を用いて求め、この値ｘを桁数がｋであるＮ進数の
最下位桁の値Ｍ0 とする最下位桁復号化手段と、Ｍ0 の
値と前記暗号文データＣとを含む１次合同式を解くこと
により、桁数がｋであるＮ進数の各桁の値を下位から逐
次求める上位桁復号化手段と、このＮ進数の各桁の数値
データを順次連結し、平文データＭを復元するデータ連
結手段と、を備えたことを要旨とするＮ進表現暗号の復
号化装置である。
【００８６】また、請求項３６記載の発明は、請求項３
５に記載のＮ進表現暗号の復号化装置において、前記上
位桁復号化手段は、前記Ｍ0 を最下位桁の値とし桁数が
ｋであるＮ進数として表現したデータ全体を２乗した形
である暗号文を、前記２乗を展開して得られるＮに関す
るｋ−１次の多項式に対応させ、該ｋ−１次の多項式の
それぞれの係数値を、前記複数の平文ブロックを変数と
する多項式関数とみなして、前記暗号文データ及び前記
Ｎ進数の既に求められた下位の桁の値に基づいて、この
ｋ−１次の式の係数値を昇順に順次求め、この求めた係
数値を使って、Ｎを法とする１次合同式を解くことによ
り、前記Ｎ進数におけるより上位の桁の値を順次確定し
ていくことを要旨とする。
【００８７】また、請求項３７記載の発明は、請求項３
５に記載のＮ進表現暗号の復号化装置において、前記ｋ
桁のＮ進数の各桁の値をＭi （０≦ｉ≦ｋ−１）とする
とき、前記上位桁復号化手段は、前記最下位桁の値Ｍ0
と、公開鍵データＮと、暗号文データＣと、ブロック数
データｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基
づいてＭi を求める同一の写像もしくは同一の計算式に
より、再帰的にＭ1 からＭk-1 までを順次復号化するこ
とを要旨とする。
【００８８】また、請求項３８記載の発明は、認証対象
である認証文データＭと、それぞれｐとｑとを値とする
２つの素数データで構成される秘密鍵データと、ｐとｑ
との積Ｎを値とする公開鍵データと、２以上の整数であ
るｋを値とするブロック数データと、を用いたＮ進表現
暗号による認証方法であって、前記認証文データＭに基
づいて認証子データｈ(Ｍ)を生成する第１の過程と、前
記秘密鍵データ及び前記公開鍵データを用いて、前記認
証子データｈ(Ｍ)をｋ桁のＮ進数に暗号化したときの最
下位桁の値ｈ(Ｃ)0 を生成する第２の過程と、前記最下
位桁の値を用いて、前記ｋ桁のＮ進数の上位の桁の値を
順次暗号化する第３の過程と、前記Ｎ進数の各桁の値を
順次連結して、暗号化認証子データｈ(Ｃ)を生成する第
４の過程と、前記暗号化認証子データｈ(Ｃ)と認証文デ
ータＭとを通信する第５の過程と、前記暗号化認証子デ
ータｈ(Ｃ)をｋ個のブロックに分割するとともに、この
分割された各ブロックの値をＮ進数の各桁の値とした結
合データを求める第６の過程と、この結合データ全体を
２乗した値からＮのｋ乗を法とする剰余を求めることに
より暗号化認証子データｈ(Ｃ)を復号化して復号化認証
子データｈ(Ｍ)′を得る第７の過程と、この復号化認証
子データｈ(Ｍ)′と前記認証文データＭとを用いて認証
を行う第８の過程と、を備えたことを要旨とする公開鍵
型のＮ進表現暗号による認証方法である。
【００８９】また、請求項３９記載の発明は、認証対象
となる認証文データＭと、それぞれｐとｑとを値とする
２つの素数データで構成される秘密鍵データと、ｐとｑ
との積Ｎを値とする公開鍵データと、を用いて、前記認
証子データｈ(Ｍ)を暗号化した暗号化認証子データｈ
(Ｃ)を生成するＮ進表現暗号による認証文生成方法であ
って、前記認証文データＭをハッシュ化して認証子デー
タｈ(Ｍ)を生成する第１の過程と、自然数の中から、そ
の値ｘを２乗した値が、Ｎを法として前記認証子データ
ｈ(Ｍ)に等しくなるような自然数ｘを、数値ｐを法とす
る剰余ならびに数値ｑを法とする剰余を用いて求め、こ
の自然数の値ｘを桁数がｋであるＮ進数の最下位桁の値
ｈ(Ｃ)0 とする第２の過程と、この最下位桁の値ｈ(Ｃ)
0 と前記認証子データｈ(Ｍ)を含む１次合同式を解くこ
とにより、桁数がｋであるＮ進数の各桁の数値を下位か
ら順次求める第３の過程（以下、この過程を認証子上位
桁暗号化過程と称する）と、この求められた各桁の数値
を順次連結し、全体として１つのＮ進数データとするこ
とによって、暗号化認証子データｈ(Ｃ)を生成する第４
の過程と、を備えたことを要旨とするＮ進表現暗号によ
る認証文生成方法である。
【００９０】また、請求項４０記載の発明は、請求項３
９に記載のＮ進表現暗号による認証文生成方法におい
て、前記認証子上位桁暗号化過程は、前記ｈ(Ｃ)0 を最
下位桁の値とし桁数がｋであるＮ進数として表現したも
のを全体を２乗した形である暗号文を、前記２乗を展開
して得られるＮに関するｋ−１次の多項式に対応させ、
該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
平文ブロックを変数とする多項式関数とみなして、前記
暗号文データ及び前記Ｎ進数の既に求められた下位の桁
の値に基づいて、このｋ−１次の式の係数値を昇順に順
次求め、求めた係数値を使って、Ｎのべき乗を法とする
１次合同式を解くことにより、前記Ｎ進数における上位
の桁の値を順次確定していくことによって実現すること
を要旨とする。
【００９１】また、請求項４１記載の発明は、請求項３
９に記載のＮ進表現暗号による認証文生成方法におい
て、前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i （０≦ｉ≦
ｋ−１）とするとき、前記認証子上位桁暗号化過程は、
前記最下位桁の値ｈ(Ｃ)0 と、公開鍵データＮと、認証
子データｈ(Ｍ)と、ブロック数データｋとを入力とし
て、ｈ(Ｃ)0 ，ｈ(Ｃ)1 ，…，ｈ(Ｃ)i-1 に基づいてｈ
(Ｃ)i を求める同一の写像もしくは同一の計算式によ
り、再帰的にｈ(Ｃ)1 からｈ(Ｃ)k-1 までを順次暗号化
することを要旨とする。
【００９２】また、請求項４２記載の発明は、認証対象
となる認証文データＭと、それぞれｐとｑとを値とする
２つの素数データで構成される秘密鍵データと、ｐとｑ
との積Ｎを値とする公開鍵データと、を用いて、前記認
証子データｈ(Ｍ)を暗号化した暗号化認証子データｈ
(Ｃ)を生成するＮ進表現暗号による認証文生成プログラ
ムを格納した記憶媒体であって、前記認証文データＭを
ハッシュ化して認証子データｈ(Ｍ)を生成し、自然数の
中から、その値ｘを２乗した値が、Ｎを法として前記認
証子データｈ(Ｍ)に等しくなるような自然数ｘを、数値
ｐを法とする剰余ならびに数値ｑを法とする剰余を用い
て求め、この自然数の値ｘを桁数がｋであるＮ進数の最
下位桁の値ｈ(Ｃ)0 とし、この最下位桁の値ｈ(Ｃ)0 と
前記認証子データｈ(Ｍ)を含む１次合同式を解くことに
より、桁数がｋであるＮ進数の各桁の数値を下位から順
次求め、この求められた各桁の数値を順次連結し、全体
として１つのＮ進数データとすることによって、暗号化
認証子データｈ(Ｃ)を生成する、ことを要旨とするＮ進
表現暗号による認証文生成プログラムを記憶した記憶媒
体である。
【００９３】また、請求項４３記載の発明は、認証対象
となる認証文データＭと、それぞれｐとｑとを値とする
２つの素数データで構成される秘密鍵データと、ｐとｑ
の積Ｎを値とする公開鍵データと、を用いて、前記認証
文データＭに基づいて生成された認証子データｈ(Ｍ)を
暗号化した暗号化認証子データｈ(Ｃ)を生成するＮ進表
現暗号による認証文生成装置であって、前記認証文デー
タＭをハッシュ化して認証子データｈ(Ｍ)を生成するハ
ッシュ化手段と、自然数の中から、その値ｘを２乗した
値が、Ｎを法として前記認証子データｈ(Ｍ)に等しくな
るような自然数ｘを、数値ｐを法とする剰余ならびに数
値ｑを法とする剰余を用いて求め、この自然数の値ｘを
桁数がｋであるＮ進数の最下位桁の値ｈ(Ｃ)0 とする最
下位桁暗号化手段と、この最下位桁の値ｈ(Ｃ)0 と前記
認証子データｈ(Ｍ)を含む１次合同式を解くことによ
り、桁数がｋであるＮ進数の各桁の数値を下位から順次
求める認証子上位桁暗号化手段と、この求められた各桁
の数値を順次連結し、全体として１つのＮ進数データと
することによって、暗号化認証子データｈ(Ｃ)を生成す
る連結手段と、を備えたことを要旨とするＮ進表現暗号
による認証文生成装置である。
【００９４】また、請求項４４記載の発明は、請求項４
３に記載のＮ進表現暗号による認証文生成装置におい
て、前記認証子上位桁暗号化手段は、前記ｈ(Ｃ)0 を最
下位桁の値とし桁数がｋであるＮ進数として表現したも
のを全体を２乗した形である暗号文を、前記２乗を展開
して得られるＮに関するｋ−１次の多項式に対応させ、
該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
平文ブロックを変数とする多項式関数とみなして、前記
暗号文データ及び前記Ｎ進数の既に求められた下位の桁
の値に基づいて、このｋ−１次の式の係数値を昇順に順
次求める係数値計算手段と、この求められた係数値を使
って、Ｎのべき乗を法とする１次合同式を解くことによ
り、前記Ｎ進数におけるより上位の桁の値を順次確定し
ていく上位桁計算手段と、を備えることを要旨とする。
【００９５】また、請求項４５記載の発明は、請求項４
３に記載のＮ進表現暗号による認証文生成装置におい
て、前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i （０≦ｉ≦
ｋ−１）とするとき、前記認証子上位桁暗号化手段は、
前記最下位桁の値ｈ(Ｃ)0 と、公開鍵データＮと、認証
子データｈ(Ｍ)と、ブロック数データｋとを入力とし
て、ｈ(Ｃ)0 ，ｈ(Ｃ)1 ，…，ｈ(Ｃ)i-1 に基づいてｈ
(Ｃ)i を求める同一の写像もしくは同一の計算式によ
り、再帰的にｈ(Ｃ)1 からｈ(Ｃ)k-1 までを順次暗号化
することを要旨とする。
【００９６】また、請求項４６記載の発明は、認証対象
となる認証文データＭと、前記請求項３９、４０、４
１、４３、４４、４５のいずれか一項に記載の方法また
は装置で暗号化された暗号化認証子ｈ(Ｃ)データと、そ
れぞれｐとｑとを値とする２つの素数データで構成され
た秘密鍵データ同士の積Ｎを値とする公開鍵データと、
を用いて、前記認証文データＭ及びまたは前記暗号化認
証子データｈ(Ｃ)が正当であるか否かを判別するＮ進表
現暗号による認証文検証方法であって、暗号化認証子デ
ータｈ(Ｃ)を２乗した値に対して、Ｎのｋ乗を法とする
剰余である復号化認証子データｈ(Ｍ)を求め、この復号
化認証子データｈ(Ｍ)と、前記認証対象となる認証文デ
ータＭをハッシュ化したハッシュ化認証子データｈ
(Ｍ)′が一致していた場合は、一連の認証ないし検証過
程が正常であったと判定し、この復号化認証子データｈ
(Ｍ)と、前記認証対象となる認証文データＭをハッシュ
化したハッシュ化認証子データｈ(Ｍ)′が不一致であっ
た場合は、一連の認証ないし検証過程のいずれかに異常
があったと判定する、ことを要旨とするＮ進表現暗号に
よる認証文検証方法である。
【００９７】また、請求項４７記載の発明は、認証対象
となる認証文データＭと、前記請求項３９、４０、４
１、４３、４４、４５のいずれか一項に記載の方法また
は装置で暗号化された暗号化認証子ｈ(Ｃ)データと、そ
れぞれｐとｑとを値とする２つの素数データで構成され
た秘密鍵データ同士の積Ｎを値とする公開鍵データと、
を用いて、前記認証文データＭ及びまたは前記暗号化認
証子データｈ(Ｃ)が正当であるか否かを判別するＮ進表
現暗号による認証文検証プログラムを格納した記憶媒体
であって、暗号化認証子データｈ(Ｃ)を２乗した値に対
して、Ｎのｋ乗を法とする剰余である復号化認証子デー
タｈ(Ｍ)を求め、この復号化認証子データｈ(Ｍ)と、前
記認証対象となる認証文データＭをハッシュ化したハッ
シュ化認証子データｈ(Ｍ)′が一致していた場合は、一
連の認証ないし検証過程が正常であったと判定し、この
復号化認証子データｈ(Ｍ)と、前記認証対象となる認証
文データＭをハッシュ化したハッシュ化認証子データｈ
(Ｍ)′が不一致であった場合は、一連の認証ないし検証
過程のいずれかに異常があったと判定する、ことを要旨
とするＮ進表現暗号による認証文検証プログラムを格納
した記憶媒体である。
【００９８】また、請求項４８記載の発明は、認証対象
となる認証文データＭと、前記請求項３９、４０、４
１、４３、４４、４５のいずれか一項に記載の方法また
は装置で暗号化された暗号化認証子ｈ(Ｃ)データと、そ
れぞれｐとｑとを値とする２つの素数データで構成され
た秘密鍵データ同士の積Ｎを値とする公開鍵データと、
を用いて、前記認証文データＭ及びまたは前記暗号化認
証子データｈ(Ｃ)が正当であるか否かを判別するＮ進表
現暗号による認証文検証装置であって、前記暗号化認証
子データｈ(Ｃ)を２乗した値に対して、Ｎをｋ乗した数
値を法とする剰余である復号化認証子データｈ(Ｍ)を生
成する認証子復号化手段と、前記認証文データＭをハッ
シュ化してハッシュ化認証子データｈ(Ｍ)′を生成する
ハッシュ化手段と、前記復号化認証子データｈ(Ｍ)と、
前記ハッシュ化記認証子データｈ(Ｍ)′とを比較し、両
者が一致していた場合は、一連の認証ないし検証過程が
正常であったと判定し、両者が不一致であった場合は、
一連の認証ないし検証過程のいずれかに異常があったと
判定する照合判定手段と、を備えたことを要旨とするＮ
進表現暗号による認証文検証装置である。
【００９９】本発明においては、公開鍵Ｎを基数とする
Ｎ進表現を暗号化に用いることにより、これに対応する
復号化の速度を大幅に高速化することができる。すなわ
ち、Ｎ進表現された最下位桁の復号は、従来と同様の復
号化方法により復号化されるが、Ｎ進表現された最下位
桁を除く上位桁は、復号化された最下位桁の値を利用し
て、１次合同式を解くことにより復号化することができ
る。
【０１００】その結果、従来のＲＳＡ型暗号やラビン型
暗号と同等の強度を持つ公開鍵暗号を構成することがで
きる。また、復号化速度では、従来のＲＳＡ型暗号やラ
ビン型暗号より高速にすることができる。また、本方式
および装置は、認証にも適用でき、暗号化通信および認
証の双方に対称使用が可能となる。
【０１０１】また、本発明において、一ブロック目を公
開鍵Ｎのビット長程度の任意の乱数とし、二ブロック目
以降に平文を埋め込むことにより、暗号化の冪乗過程で
乱数のランダム性が後続ブロックの統計的性質を覆い隠
すこととなり、ＲＳＡ暗号やラビン暗号に知られている
同報通信攻撃などに弱いという欠点を克服できる。
【０１０２】このとき使用される乱数は、暗号通信の送
信側で任意に生成したものでよく、１回限りの使い捨て
乱数とすることが好ましい。また受信側では、単に復号
結果から乱数部を切り捨てることになり、送信側で使用
する乱数と同一乱数を受信側で共有する必要はないの
で、乱数伝達の為の手段は不要である。
【０１０３】
【発明の実施の形態】次に、図面を参照して本発明の実
施の形態を詳細に説明する。 ［ＲＳＡ型暗号化通信装置］図１は、本発明に係るＮ進
表現暗号をＲＳＡ型公開鍵暗号に適用した実施の形態を
示す暗号化通信装置の構成を示すブロック図である。
尚、以下の詳細説明においては、Ｎ進数または基数Ｎを
小文字のｎを使用してｎ進数または基数ｎと表記するこ
ともある。
【０１０４】図１によれば、暗号化通信装置１１は、鍵
生成処理部２１と、暗号化装置３１と、復号化装置４１
と通信路５１とを備えて構成されている。
【０１０５】［鍵生成処理部］鍵生成処理部２１は、従
来の公開鍵型暗号と同等の鍵生成機能を有するものであ
り、独立した装置として実現されてもよいし、後述され
る復号化装置４１に含まれても良い。鍵生成処理部２１
は、秘密鍵１である２個の素数ｐ，ｑを生成し、その積
ｎ＝ｐｑを計算し、公開鍵１とする。次いで、素数ｐ，
ｑから後述されるＬを計算し、公開鍵２であるｅと、秘
密鍵２であるｄを生成する。
【０１０６】［暗号化装置］暗号化装置３１は、平文分
割処理部３３と、データ結合部３５と、暗号化処理部３
７とを備えて構成され、平文Ｍを暗号化した暗号文Ｃを
生成し、通信路５１を介して復号化装置４１へ送信する
ものである。
【０１０７】平文分割処理部３３は、ｎの剰余類の範囲
内の大きさのｋ個のブロックに分割された分割平文（Ｍ
0 ，Ｍ1 ，…，Ｍk-1 ）を生成し、データ結合処理部３
５へ引き渡す。
【０１０８】データ結合処理部３５は、次の式（２３）
に示すように、１つのｎ進数Ｍ（ｎ）の各桁の値が分割
平文の各ブロックＭi （０≦ｉ≦ｋ−１）となるよう
に、それぞれのブロックのデータを結合したｋ桁のｎ進
数表現を行い、このｎ進数Ｍ（ｎ）を暗号化処理部へ引
き渡す。
【０１０９】
【数１８】 Ｍ（ｎ）＝Ｍ0 ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1 Ｍk-1 …(23) 暗号化処理部３７は、データ結合処理部３５から受けた
ｎ進数Ｍ（ｎ）を受け手の公開鍵２であるｅを用いて、
【数１９】 Ｃ≡（Ｍ（ｎ））e （ mod ｎk ） ≡（Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e （ mod ｎk ） …(24) 式（２４）によって暗号化を行ない、通信路５１を介し
て復号化装置４１に対して送信する。
【０１１０】［復号化装置］一方、復号化装置４１は、
最下位桁復号化処理部４３と、上位桁復号化処理部４５
と、データ連結処理部４７とを備えて構成され、通信路
５１を介して受信した暗号文Ｃから、分割平文（Ｍ0 ，
Ｍ1 ，…，Ｍk-1 ）を復号化し、これらを連結して、元
の平文Ｍを復元するものである。
【０１１１】最下位桁復号化処理部４３は、自らの秘密
鍵２であるｄを用いて、
【数２０】 Ｍ0 ≡Ｃd （ mod ｎ） …(25) 式（２５）により最下位桁であるブロックＭ0 を復号化
し、上位桁復号化処理部４５へ引き渡す。
【０１１２】上位桁復号化処理部４５は、Ｍ0 を利用し
て、ｎを法とする１次合同式を解くことにより、最下位
桁Ｍ0 を除く上位桁のブロックＭ1 ，Ｍ2 ，…，Ｍk-1
を順次復号化し、Ｍ0 とともに、データ連結処理部４７
へ引き渡す。
【０１１３】データ連結処理部４７は、復号化された分
割平文（Ｍ0 ，Ｍ1 ，…，Ｍk-1 ）を統合し、原平文Ｍ
へ復元する。
【０１１４】次に、本実施の形態の動作を詳細に説明す
る。
【０１１５】［鍵生成処理部］まず、鍵生成処理部２１
の動作を説明する。鍵生成処理部２１により生成される
秘密鍵と公開鍵との組は、暗号化通信にも認証にも使用
可能であるので、以下の説明では、特に暗号化・復号化
鍵と、認証文生成・認証文検証鍵とを区別することはし
ない。
【０１１６】鍵生成の最初は、暗号の所要強度に応じた
桁数を持つ２つの有理素数を生成する。秘密鍵１は、こ
の２個の有理素数ｐ，ｑとする。公開鍵１は、それらの
積ｎ＝ｐｑとする。また、秘密鍵１、ｐ，ｑに対して、
ＬＣＭを最小公倍数を求める関数とするとき、
【数２１】 Ｌ＝ＬＣＭ（ｐ−１，ｑ−１） …(26) を求める。次に、ＧＣＤを最大公約数を求める関数とす
るとき、
【数２２】 ｅｄ≡１( mod Ｌ)，ＧＣＤ(ｅ，Ｌ)＝ＧＣＤ(ｅ，ｎ)＝１ …(27) を満たす、ｅ，ｄを求める。秘密鍵２はｄとし、公開鍵
２はｅとする。これらの鍵を生成する装置の機能図を、
図７に示す。
【０１１７】［平文分割処理部］図８は、平文分割処理
部３３の概略動作を示すフローチャート図である。平文
分割処理部３３の初期状態として、平文Ｍのビット列、
分割ブロック数ｋ、分割平文長［ｌｏｇ2ｎ］（ここ
で、［ｘ］は、ｘを超えない最大整数を示すガウス記号
である）、がそれぞれ与えられるものとする。
【０１１８】まず、制御変数ｉを０に初期設定する（ス
テップＳ２０１）。次いで、Ｍの先頭より［ｌｏｇ
2ｎ］ビット長のブロックＭi を切り出し、残りのビッ
ト列を新たなＭとする（ステップＳ２０３）。次いで、
ｉとｋ−１とを比較し（ステップＳ２０５）、等しくな
ければｉを１だけ増加させて（ステップＳ２０７）、ス
テップＳ２０３へ戻る。ステップＳ２０５の比較結果、
等しければ、Ｍ0，Ｍ1，…，ＭK-1 をデータ結合処理部
３５へ出力する（ステップＳ２０９）。次いで、Ｍが空
であるか否かを判定し（ステップＳ２１１）、空でなけ
れば、ステップＳ２０１へ戻る。空であれば、処理を終
了する。
【０１１９】なお、フローチャートには示さなかった
が、最後のブロックのパディングには、通常用いられる
ブランクや０に代えて、任意に発生された乱数を用いて
も良い。
【０１２０】［データ結合処理部］データ結合処理部３
５は、１つのｎ進数Ｍ（ｎ）の各桁の値が分割平文の各
ブロックＭi （０≦ｉ≦ｋ−１）となるように、それぞ
れのブロックのデータを結合したｎ進数表現を行い、こ
のｎ進数Ｍ（ｎ）を暗号化処理部へ引き渡す。
【０１２１】
【数２３】 Ｍ（ｎ）＝Ｍ0 ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1 Ｍk-1 …(28)
【０１２２】［暗号化処理部］暗号化処理部３７は、デ
ータ結合処理部３５から受けたｎ進数Ｍ（ｎ）を受け手
の公開鍵２であるｅと公開鍵１であるｎとを用いて、
【数２４】 Ｃ≡（Ｍ（ｎ））e （ mod ｎk ） ≡（Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e （ mod ｎk ） …(29) 式（２９）によって暗号化を行ない、暗号文Ｃを通信路
５１を介して復号化装置４１へ送信する。
【０１２３】［最下位桁復号化処理部］復号化装置４１
の最下位桁復号化処理部４３は、送られてきた暗号文Ｃ
に対して、公開鍵１：ｎと、秘密鍵２：ｄとを用いて、
【数２５】 Ｍ0 ≡Ｃd （ mod ｎ） …(30) 式（３０）を計算し、ｎ進表現の最下位桁であるＭ0 を
復号化する。この復号化関数は、通常のＲＳＡ型公開鍵
暗号と同じ復号化関数であり、Ｍ0 の復号化は、従来の
ＲＳＡ型公開鍵暗号と同等の安全性を有しているという
ことができる。
【０１２４】［上位桁復号化処理部］復号化装置４１の
上位桁復号化処理部４５は、その詳細を図３に示すよう
に、係数計算部４５ａと、上位桁計算部４５ｂとを備え
て構成されている。さらに、係数計算部４５ａは、係数
テーブル記憶部４５ｃと、この係数テーブル記憶部４５
ｃの読出し書き込みを制御する読出・書込制御部４５ｄ
とを備えて構成されている。
【０１２５】上位桁復号化処理部４５の上位桁復号化に
おいて、最下位桁Ｍ0 を除く上位桁Ｍi （１≦ｉ≦ｋ−
１）は、
【数２６】 Ｃ≡（Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e （ｍｏｄ ｎk ） …(31) 暗号化を示す式（３１）を展開して得られる後述の展開
式（３２）から、上位桁計算部４５ｂにより１次合同式
を解くことにより順次帰納的に求めることができる。
【０１２６】ここで、式（３１）の右辺（Ｍ0 ＋ｎＭ1
＋…＋ｎk-1 Ｍk-1 ）e の展開式のｎi （０≦ｉ≦ｋ−
１）の係数をＫi とする。すなわち、
【数２７】 （Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e ＝ｎ0 Ｋ0 ＋ｎ1 Ｋ1 ＋ｎ2 Ｋ2 ＋…＋ｎk-1 Ｋk-1 ＋…＋ｎe(k-1)Ｋe(k-1) …(32) とする（Ｋi の計算は次節に記述する）。ここで、Ｋ0
，Ｋ1 ，Ｋ2 ，…，Ｋk-1 は、Ｍ0 ，Ｍ1 ，Ｍ2 ，
…，Ｍk-1 を変数とする多項式関数であり、Ｍ0 ，Ｍ1
，Ｍ2 ，…，Ｍk-1 のそれぞれの値を入力することに
より整数値を出力する。関数Ｋ0 ，Ｋ1 ，Ｋ2 ，…，Ｋ
k-1 の具体的な式については後述する。なお、Ｋk ，Ｋ
k+1 ，…，Ｋe(k-1)については、復号処理に使用しない
ため考察を省略する。
【０１２７】また、計算の便宜上、Ｋ'iを次のように定
義する。
【０１２８】
【数２８】 Ｋ'i＝Ｋi −ｅＭ0 e-1 Ｍi （１≦ｉ＜ｋ−１） …(33) ここで、Ｋ'1 ，Ｋ'2 ，…，Ｋ'k-1 は、Ｋ0 ，Ｋ1 ，
Ｋ2 ，…，Ｋk-1 と同じように、Ｍ0 ，Ｍ1 ，Ｍ2 ，
…，Ｍk-2 を変数とする多項式関数であり、Ｍ0 ，Ｍ1
，Ｍ2 ，…，Ｍk-2 のそれぞれの値を入力することに
より整数値を出力する。但し、Ｋ'iはＭi の値に依存し
ないことに注意を要する。
【０１２９】次にＭ1 の求め方について説明する。Ｋ0
及びＫ'1は、Ｍ0 のみを変数とする多項式関数であり、
前項までに復号化されたＭ0 を入力することにより整数
値を出力するものである。その出力値Ｋ0 ，Ｋ'1を用い
て、
【数２９】 とするとき、合同式
【数３０】 ｅＭ0 e-1 ｘ≡ｂ1 （ｍｏｄ ｎ） …(35) をみたすｘを求めることにより、Ｍ1 を復号化する。
【０１３０】次にＭ2 の求め方について説明する。Ｋ0
，Ｋ1 ，及びＫ'2 は、Ｍ0 ，Ｍ1のみを変数とする多
項式関数であり、前項までに復号化されたＭ0 ，Ｍ1 を
入力することにより整数値を出力するものである。その
出力値Ｋ0 ，Ｋ1，Ｋ'2を用いて、
【数３１】 とするとき、合同式
【数３２】 ｅＭ0 e-1 ｘ≡ｂ2 （ｍｏｄ ｎ） …(37) をみたすｘを求めることにより、Ｍ2 を復号化する。以
下、同様にＭ3 ，Ｍ4 ，…が計算できる。
【０１３１】次に、Ｍk-2 までの求められた値を用い
て、Ｍk-1 を求める方法について説明する。Ｋ0 ，Ｋ1
，…，Ｋk-2 ，及びＫ'k-1は、Ｍ0 ，Ｍ1 ，…，Ｍk-2
のみを変数とする多項式関数であり、前項までに復号
化されたＭ0 ，Ｍ1 ，…，Ｍk-2を入力することにより
整数値を出力するものである。その出力値Ｋ0 ，Ｋ1，
…，Ｋk-2 ，Ｋ'k-1を用いて、
【数３３】 とするとき、合同式
【数３４】 ｅＭ0 e-1 ｘ≡ｂk-1 （ｍｏｄ ｎ） …(39) をみたすｘを求めることにより、Ｍk-1 を復号化する。
【０１３２】［（Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e
の展開式］本発明で必要となる（Ｍ0 ＋ｎＭ1 ＋…＋ｎ
k-1 Ｍk-1 ）e の展開式に於けるｎi の係数Ｋi （ｉ＝
０，１，２，…，ｋ−１）の求め方を以下に記述する。
【０１３３】乗法の分配法則から導かれる多項定理よ
り、
【数３５】 であり、ｎi の係数は、
【数３６】 Γi ＝｛ｓ0 ，ｓ1 ，…，ｓk-1 ｜ｓ1 ＋２ｓ2 ＋…＋（ｋ−１）ｓk-1 ＝ｉ， ０≦ｓ0 ，ｓ1 ，…，ｓk-1 ≦ｅ， ｓ0 ＋ｓ1 ＋…＋ｓk-1 ＝ｅ｝ …(41) をみたす集合Γi を求め、
【数３７】 を計算することにより求まる。
【０１３４】実際に、ｉが小さい場合を以下に記述す
る。
【０１３５】
【数３８】 Ｋ0 ＝ＭO e Ｋ1 ＝ｅＭ0 e-1 Ｍ1 Ｋ2 ＝ eＣ2 Ｍ0 e-2 Ｍ1 2 ＋ｅＭ0 e-1 Ｍ2 Ｋ3 ＝ eＣ3 Ｍ0 e-3 Ｍ1 3 ＋２ eＣ2 Ｍ0 e-1 Ｍ1 Ｍ2 ＋ｅＭ0 e-1 Ｍ3 Ｋ4 ＝ eＣ4 Ｍ0 e-4 Ｍ1 5 ＋３ eＣ4 Ｍ0 e-3 Ｍ1 2 Ｍ2 ＋ eＣ2 Ｍ0 e-2 Ｍ2 2 ＋ｅＭ0 e-1 Ｍ4 Ｋ5 ＝ eＣ5 Ｍ0 e-5 Ｍ1 5 ＋３ eＣ4 Ｍ0 e-4 Ｍ1 3 Ｍ2 ＋３ eＣ3 Ｍ0 e-3 Ｍ1 Ｍ2 2 ＋２ eＣ2 Ｍ0 e-2 Ｍ2 Ｍ3 ＋２ eＣ3 Ｍ0 e-2 Ｍ1 Ｍ4 ＋ｅＭ0 e-1 Ｍ5 Ｋ6 ＝ eＣ6 Ｍ0 e-6 Ｍ1 6 ＋５ eＣ5 Ｍ0 e-5 Ｍ1 4 Ｍ2 ＋４ eＣ4 Ｍ0 e-4 Ｍ1 3 Ｍ3 ＋３ eＣ3 Ｍ0 e-3 Ｍ1 2 Ｍ4 ＋ eＣ3 Ｍ0 e-3 Ｍ2 3 ＋e Ｃ2 Ｍ0 e-2 Ｍ3 2 ＋２ eＣ2 Ｍ0 e-2 Ｍ2 Ｍ4 ＋２ eＣ2 Ｍ0 e-2 Ｍ1 Ｍ5 ＋ｅＭ0 e-1 Ｍ6 Ｋ7 ＝ eＣ7 Ｍ0 e-7 Ｍ1 7 ＋６ eＣ6 Ｍ0 e-6 Ｍ1 5 Ｍ2 ＋５ eＣ5 Ｍ0 e-5 Ｍ1 4 Ｍ3 ＋ 5Ｃ2eＣ5 Ｍ0 e-5 Ｍ1 3 Ｍ2 2 ＋ eＣ4 Ｍ0 e-4 Ｍ1 3 Ｍ4 ＋２ 4Ｃ2eＣ4 Ｍ0 e-4 Ｍ1 2 Ｍ2 Ｍ3 ＋４ eＣ4 Ｍ0 e-4 Ｍ1 Ｍ2 3 ＋３ eＣ3 Ｍ0 e-3 Ｍ1 2 Ｍ5 ＋３ eＣ3 Ｍ0 e-3 Ｍ1 Ｍ3 2 ＋３ eＣ3 Ｍ0 e-3 Ｍ2 2 Ｍ3 ＋２ eＣ2 Ｍ0 e-2 Ｍ1 Ｍ6 ＋２ eＣ2 Ｍ0 e-2 Ｍ2 Ｍ5 ＋２ eＣ2 Ｍ0 e-2 Ｍ3 Ｍ4 ＋ｅＭ0 e-1 Ｍ7 … Ｋk-1 ＝ ｛Ｍ0 ，Ｍ1 ，…，Ｍk-1 の多項式｝ …(43) ここで、 xＣy は、相異なるｘ個からｙ個の元を取り出
す組合せ（の数）である。係数計算部４５ａは、この式
（４３）に基づいて、係数Ｋi を順次計算し、係数テー
ブル記憶部４５ｃに格納する。
【０１３６】［データ連結処理部］次に、データ連結処
理部４７は、最下位桁復号化処理部４３及び上位桁復号
化処理部４５によって得られる分割平文（Ｍ0 ，Ｍ1 ，
…，Ｍk-1 ）を順番に連結し原平文Ｍを得る。
【０１３７】次に、この暗号化通信装置１１の動作をフ
ローチャート及びメモリ上のデータ配置を示す表を参照
しながら、詳細に説明する。
【０１３８】図９は、本発明に係るｎ進表現暗号をＲＳ
Ａ型公開鍵暗号に適用した場合の鍵生成処理を示すフロ
ーチャートであり、表１は、同処理におけるメモリ上の
データ配置を示す表である。なお、以下の各表におい
て、属性欄はデータの属性を示し、それぞれの処理過程
における入力、作業領域、および出力の区別を表示して
いる。
【０１３９】
【表１】 表１に示すように、データ番号１及び２に与えられた秘
密鍵１であるふたつの素数ｐ，ｑに対して、（ｐ−１）
と、（ｑ−１）との最小公倍数であるＬを求め、これを
データ番号３に格納する（ステップＳ３０１）。
【０１４０】次いで、ｅｄ≡１（ｍｏｄ Ｌ），ＧＣＤ
（ｅ，Ｌ）＝ＧＣＤ（ｅ，ｎ）＝１となる２数ｅ，ｄを
求め、それぞれ公開鍵２および秘密鍵２として、それぞ
れデータ番号４及び５に格納して（ステップＳ３０
３）、鍵生成処理を終了する。
【０１４１】図１０は、暗号化装置３１の暗号化送信処
理の動作を示すフローチャートであり、表２は、同処理
におけるメモリ上のデータ配置を示す表である。
【０１４２】
【表２】 表２に示すように、暗号化送信処理は、公開鍵１ｎ及び
公開鍵２ｅがそれぞれデータ番号１、２に与えられ、さ
らに、分割平文長［ｌｏｇ2ｎ］及び平文Ｍがデータ番
号４及び５に与えられる。なお、ここでは分割ブロック
数ｋは、分割の結果として得られるものとしたが、最初
から定数が与えられ、この定数の分割ブロック毎に暗号
化を行うことも可能である。
【０１４３】図１０によれば、まず、データ番号５の平
文Ｍを読出し、その先頭から、それぞれ［ｌｏｇ2ｎ］
ビット長のｋ個の平文ブロックＭi （０≦ｉ≦ｋ−１）
を切り出し、各平文ブロックをデータ番号６から５＋ｋ
までに順次格納し、データ番号５には、切り出した残り
のメッセージＭ′を格納する（ステップＳ４０１）。
【０１４４】次いで、データ番号６から５＋ｋまでのｋ
個の平文ブロックに対して、ｎ進数、Ｍ（ｎ）＝Ｍ0 ＋
ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1Ｍk-1を求める（ステップ
Ｓ４０３）。
【０１４５】次いで、データ番号１、２の公開鍵１ｎ及
び公開鍵２ｅを用いて、Ｃ≡｛Ｍ（ｎ）｝e （ mod
ｎk）を求め、暗号文Ｃとして、データ番号５＋ｋ＋１
に格納する（ステップＳ４０５）。次いで、データ番号
５＋ｋ＋１の暗号文を送信し（ステップＳ４０７）、デ
ータ番号５にメッセージが残っているか否かを調べる
（ステップＳ４０９）。メッセージが残っていれば、ス
テップＳ４０１へ戻る。メッセージが残っていなけれ
ば、終了する。
【０１４６】図１１は、復号化装置４１の受信復号化処
理の動作を示すフローチャートであり、表３は、同処理
におけるメモリ上のデータ配置を示す表である。
【０１４７】
【表３】 表３に示すように、受信復号化処理においては、データ
番号１に公開鍵１ｎ及び公開鍵２ｅが与えられ、データ
番号２に秘密鍵２ｄが与えられ、さらに、分割ブロック
数ｋ及び分割平文長［ｌｏｇ2ｎ］がデータ番号３及び
４に与えられる。また、暗号文Ｃは、データ番号４＋２
ｋ＋１に与えられ、データ番号５から４＋２ｋまで及び
４＋２ｋ＋２から４＋３ｋ＋１までは作業領域として使
用され、結果の統合平文はデータ番号４＋３ｋ＋２に格
納される。
【０１４８】図１１によれば、まず、データ番号４＋２
ｋ＋１の暗号文Ｃに対して、データ番号１、２の公開鍵
１ｎ、秘密鍵２ｄを使用して、（ｍｏｄ ｎ）のもとで
ｄ乗演算を行い、ｎ進表現された平文の最下位桁である
平文ブロックＭ0 を復元し、その結果をデータ番号４＋
２ｋ＋２に格納する（ステップＳ５０１）。
【０１４９】次いで、ｎ進表現された平文を法ｎkのも
とでｅ乗した式を展開したときのｎ0の項の係数である
Ｋ0 を、先に求めたＭ0 と公開鍵２ｅとを用いてＫ0 ＝
Ｍ0 eにより求め、データ番号５に格納する（ステップ
Ｓ５０３）。次いでｎ進表現された上位桁を順次求める
ための反復パラメータｉを１に初期設定する（ステップ
Ｓ５０５）。
【０１５０】次いで、反復パラメータｉについて、Ｍ0
，Ｍ1 ，…，Ｍi-1 を変数とする多項式関数であるＫi
-1 を、前のステップまでに求められたＭ0 ，Ｍ1 ，
…，Ｍi-1 を用いて計算し、その値（整数値）をデータ
番号４＋ｉに格納し、同様に、Ｍ0 ，Ｍ1 ，…，Ｍi-1
を変数とする多項式関数であるＫ'iを、前のステップま
でに求められたＭ0 ，Ｍ1 ，…，Ｍi-1 を用いて計算
し、その値（整数値）をデータ番号５＋ｋ＋ｉに格納す
る（ステップＳ５０６）。
【０１５１】次いで、データ番号４＋２ｋ＋１の暗号文
Ｃと、データ番号５から５＋ｉ−１のＫj （０≦ｊ≦ｉ
−１）と、データ番号５＋ｋ＋ｉのＫ'iに対して、以下
のｂi を計算する（ステップＳ５０７）。
【０１５２】
【数３９】 次いで、ユークリッドの互除法により、合同式
【数４０】 ｅＭ0 e-1 ｘ≡ｂi （ｍｏｄ ｎ） …(45) をみたすｘを求めることにより、Ｍi を復号化し、その
結果をデータ番号４＋２ｋ＋２＋ｉに格納する（ステッ
プＳ５０９）。
【０１５３】次いで、反復終了条件ｉ＝ｋ−１を判定し
（ステップＳ５１１）、成立しなければ、反復パラメー
タを１だけ増加させて（ステップＳ５１３）、ステップ
Ｓ５０７へ戻る。反復終了条件が成立すれば、データ番
号４＋２ｋ＋２から４＋３ｋ＋１までの復号化されたｋ
個の平文ブロックを連接し、そのビット列をデータ番号
４＋３ｋ＋２の末尾に連接して（ステップＳ５１５）、
処理を終了する。
【０１５４】［ＲＳＡ型暗号化通信装置の変形例］次
に、図２１は、本発明に係るＮ進表現暗号をＲＳＡ型公
開鍵暗号に適用した実施の形態の変形例を示す暗号化通
信装置の構成を示すブロック図である。本変形例では、
複数の平文ブロックＭの先頭に乱数ブロックＲを配置
し、Ｍ0 をＲで置き換えた例を説明する。これは、平文
Ｍに代えて、乱数ブロックＲと平文Ｍとを連接したＲ‖
Ｍを暗号化の対象とするとも考えられる。
【０１５５】図２１によれば、暗号化通信装置１２は、
鍵生成処理部２１と、暗号化装置３０と、復号化装置４
１と通信路５１とを備えて構成されていて、暗号化装置
３０以外の構成要素は、図１と同様であるので詳細な説
明は省略する。
【０１５６】［暗号化装置］暗号化装置３０は、乱数発
生部３２と、平文分割処理部３４と、データ結合部３５
と、暗号化処理部３７とを備えて構成され、先頭ブロッ
クＲとこれに続く平文ブロックＭ1 ，Ｍ2 ，…，ＭK-1
を暗号化した暗号文Ｃを生成し、通信路５１を介して復
号化装置４１へ送信するものである。図２１の暗号化装
置３０が図１の暗号化装置３１と異なる点は、乱数発生
部３２が追加されていることと、平文分割処理部３４に
乱数Ｒと平文Ｍとが入力されることである。
【０１５７】乱数発生部３２は、分割平文長［ｌｏｇ2
Ｎ］ビットに等しい長さの乱数Ｒを発生する。この乱数
は、数学的または論理的に発生される再現性のある擬似
乱数であってもよいし、再現性のない乱数であっても良
い。また、乱数Ｒは、復号化装置４１と共有する必要が
ないので、ホワイトノイズ等を利用した数学的、論理的
に再現性のない乱数発生手段を用いても良い。さらに、
一回の暗号化通信毎に新たな乱数Ｒを生成して使用する
ことが暗号の強度を高める点で好ましい。複数の通信相
手に対して同じＭを送る同報通信の場合にも、通信相手
毎に乱数Ｒの値を変えることにより、同報通信攻撃に対
する暗号強度が高まる。
【０１５８】平文分割処理部３４は、入力される平文Ｍ
の先頭に乱数発生部３２から与えられる乱数Ｒを連接し
てＲ‖Ｍとしたものを、ｎの剰余類の範囲内の大きさの
ｋ個のブロックに分割された分割平文（Ｒ ，Ｍ1 ，
…，Ｍk-1 ）を生成し、データ結合処理部３５へ引き渡
す。この結果、本変形例では、図１に示した実施形態の
分割平文の先頭ブロックＭ0 に代えて、乱数Ｒが配置さ
れたこととなる。これは、平文Ｍのビット列の先頭に
［ｌｏｇ2 Ｎ］ビット長の乱数Ｒを配置してＲ‖Ｍと
し、そのメッセージを改めてＭとしたと考えても良い。
【０１５９】データ結合処理部３５は、次の式（４６）
に示すように、１つのｎ進数Ｍ（ｎ）の各桁の値が乱数
Ｒまたは分割平文の各ブロックＭi （１≦ｉ≦ｋ−１）
となるように、それぞれのブロックのデータを結合した
ｋ桁のｎ進数表現を行い、このｎ進数Ｍ（ｎ）を暗号化
処理部へ引き渡す。
【０１６０】
【数４１】 Ｍ（ｎ）＝Ｒ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1 Ｍk-1 …(46) 暗号化処理部３７は、データ結合処理部３５から受けた
ｎ進数Ｍ（ｎ）を受け手の公開鍵２であるｅを用いて、
【数４２】 Ｃ≡（Ｍ（ｎ））e （ mod ｎk ） ≡（Ｒ ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）e （ mod ｎk ） …(47) 式（４７）によって暗号化を行ない、通信路５１を介し
て復号化装置４１に対して送信する。
【０１６１】［復号化装置］一方、復号化装置４１は、
最下位桁復号化処理部４３と、上位桁復号化処理部４５
と、データ連結処理部４７とを備えて図１と同様に構成
され、通信路５１を介して受信した暗号文Ｃから、分割
平文（Ｒ，Ｍ1 ，…，Ｍk-1 ）を復号化し、これらを連
結して、元の平文Ｍを復元するものである。
【０１６２】最下位桁復号化処理部４３は、自らの秘密
鍵２であるｄを用いて、
【数４３】 Ｒ ≡Ｃd （ mod ｎ） …(48) 式（４８）により最下位桁である乱数Ｒを復号化し、上
位桁復号化処理部４５へ引き渡す。
【０１６３】上位桁復号化処理部４５は、乱数Ｒを利用
して、ｎを法とする１次合同式を解くことにより、最下
位桁Ｒを除く上位桁のブロックＭ1 ，Ｍ2 ，…，Ｍk-1
を順次復号化し、データ連結処理部４７へ引き渡す。
【０１６４】データ連結処理部４７は、復号化された分
割平文（Ｍ1 ，…，Ｍk-1 ）を統合し、原平文Ｍへ復元
する。乱数Ｒはメッセージとしては必要ないものであ
り、上位桁復号化処理部４５による復号に利用されたの
ち、廃棄しても差し支えない。
【０１６５】［Ｎ進表現暗号をＲＳＡ型暗号に適用した
場合の具体例］次に、本発明に係るＮ進表現暗号をＲＳ
Ａ型暗号に適用した場合の実施の形態を具体的な数値を
用いて説明する。
【０１６６】［鍵生成処理部］２個の素数ｐ＝８６３，
ｑ＝７３３（秘密鍵１）を生成し、その積ｎ＝６３２５
７９（公開鍵１）を決定する。次に素数ｐ，ｑからＬ＝
３１５４９２を計算し、ｅ＝１２５（公開鍵２）と、ｄ
＝１１８６２５（秘密鍵２）を生成する。
【０１６７】［平文分割処理部］平文Ｍ＝１２３４５６
７８９０に対して、剰余類の範囲内の分割平文（Ｍ0 ，
Ｍ1 ）＝（１２３４５，６７８９０）を生成する。
【０１６８】［データ結合処理部及び暗号化処理部］受
け手の公開鍵２であるｅ＝１２５を用い、式
【数４４】 Ｃ≡（１２３４５＋６３２５７９×６７８９０）125 （ｍｏｄ ６３２５７９2 ）＝９１８３７２０６０３８ …(49) によって暗号化を行ない、受け手に送る。
【０１６９】［最下位桁復号化処理］受け手は自らの秘
密鍵２であるｄ＝１１８６２５を用い、式
【数４５】 Ｍ0 ＝９１８３７２０６０３８118625 （ｍｏｄ ６３２５７９）＝１２３４５ …(50) によりＭ0 を復号化する。
【０１７０】［上位桁復号化処理］６３２５７９を法と
する１次合同式
【数４６】 ５３７４４ｘ≡５９７４４ （ｍｏｄ ６３２５７９） …(51) を解くことにより、Ｍ1 ＝６７８９０を得る。
【０１７１】［データ連結処理部］復号化された分割平
文（Ｍ0 ，Ｍ1 ）＝（１２３４５，６７８９０）を統合
し、原平文Ｍ＝１２３４５６７８９０へ復元する。
【０１７２】［認証装置］次に、本発明に係るｎ進表現
暗号をＲＳＡ型公開鍵暗号に適用した実施の形態を示す
認証装置及び認証方法を説明する。図２は、本発明に係
るｎ進表現暗号をＲＳＡ型公開鍵暗号に適用した実施の
形態を示す認証装置の構成を示すブロック図である。図
２によれば、認証装置１１１は、鍵生成処理部２１と、
認証文生成装置１３１と、認証文検証装置１４１と通信
路５１とを備えて構成されている。
【０１７３】本発明のｎ進表現を用いた暗号方式を用
い、認証を行ないたい者が、自らの秘密鍵により認証文
の暗号化を行なって生成した認証子を受け手に送る方式
による認証装置を構成することができる。以下に、構成
方法を記述する。
【０１７４】［鍵生成処理部］鍵生成処理部２１は、２
個の素数ｐ，ｑ（秘密鍵１）を生成し、その積ｎ＝ｐｑ
（公開鍵１）を決定する。次に素数ｐ，ｑからＬを計算
し、ｅ（公開鍵２）と、ｄ（秘密鍵２）を生成する。こ
の鍵生成処理部２１の動作は、図１の暗号化通信装置１
１の鍵生成処理部２１の動作と全く同じである。
【０１７５】［認証文生成装置］認証文生成装置１３１
は、認証文ハッシュ化処理部１３３と、最下位桁暗号化
処理部１３５と、上位桁暗号化処理部１３７と、データ
連結処理部１３９とを備えて構成されている。
【０１７６】［認証文ハッシュ化処理部］認証文ハッシ
ュ化処理部１３３は、認証文Ｍに対して、ハッシュ関数
ｈによりハッシュ化を行い、認証子ｈ（Ｍ）を得る。た
だし、０≦ｈ（Ｍ）＜ｎk とする。
【０１７７】［最下位桁暗号化処理部］最下位桁暗号化
処理部１３５は、送り手の公開鍵１であるｎと秘密鍵２
であるｄを用いて、
【数４７】 ｈ（Ｃ）0 ≡ｈ（Ｍ）d （ｍｏｄ ｎ） …(52) 式（５２）を計算し、ｎ進表現された認証子の最下位桁
を求める。
【０１７８】［上位桁暗号化処理部］上位桁暗号化処理
部１３７は、図４に示すように、係数計算部１３７ａ
と、上位桁計算部１３７ｂと、を備えて構成され、さら
に、係数計算部１３７ａは、係数テーブル記憶部１３７
ｃとこの係数テーブル記憶部１３７ｃの読出・書込を制
御する読出・書込制御部とを備えて構成されている。
【０１７９】そして、上位桁暗号化処理部１３７は、図
１の復号化装置４１のときと同じ１次合同式を解くこと
により、ｎ進表現された認証子の最下位桁を除く上位
桁、ｈ（Ｃ）1 ，ｈ（Ｃ）2 ，…，ｈ（Ｃ）k-1 を計算
する。
【０１８０】［データ連結処理部］データ連結処理部１
３９は、ｎ進表現された認証子の最下位桁と上位桁とを
連結し、暗号化された認証子１（ｈ（Ｃ）0 ，ｈ（Ｃ）
1 ，…，ｈ（Ｃ）k-1 ）を生成する。そして、認証子１
と認証文Ｍの組を通信路５１を介して受け手である認証
文検証装置１４１に送る。
【０１８１】［認証文検証装置］認証文検証装置１４１
は、データ結合処理部１４３と、認証子復号化処理部１
４５と、認証文ハッシュ化処理部１４７と、照合判定部
１４９とを備えて構成されている。
【０１８２】［データ結合処理部］データ結合処理部１
４３は、受信した暗号化認証子の各ブロックをｎ進数の
各桁を表す数値としてデータ結合し、ｎ進数表現された
（ｈ（Ｃ）0 ＋ｎｈ（Ｃ）1 ＋…＋ｎk-1 ｈ（Ｃ）k-1
）を生成する。
【０１８３】［認証子復号化処理部］認証子復号化処理
部１４５は、送り手の公開鍵２であるｅを利用して、
【数４８】 ｈ（Ｍ）≡（ｈ（Ｃ）0 ＋ｎｈ（Ｃ）1 ＋…＋ｎk-1 ｈ（Ｃ）k-1 ）e （ｍｏｄ ｎk ） …(53) を計算することによって、認証子１を復号化する。
【０１８４】［認証文ハッシュ化処理部］認証文ハッシ
ュ化処理部１４７は、ハッシュ関数ｈを用い、認証文Ｍ
のハッシュ化ｈ（Ｍ）を行い、認証子２とする。
【０１８５】［照合判定部］照合判定部１４９は、認証
子１と認証子２とを比較照合し、これらが一致していれ
ば、認証は成功し、一致していなければ認証は不成功と
して、認証文の正当性を判断する。
【０１８６】次に、この認証装置１１１の動作をフロー
チャート及びメモリ上のデータ配置を示す表を参照しな
がら、詳細に説明する。
【０１８７】図１２及び１３は、本発明に係るｎ進表現
暗号をＲＳＡ型公開鍵暗号に適用した場合の認証文生成
処理を示すフローチャートであり、表４は、同処理にお
けるメモリ上のデータ配置を示す表である。
【０１８８】
【表４】 表４に示すように、認証文生成処理においては、公開鍵
１ｎ及び公開鍵２ｅがデータ番号１に、秘密鍵２ｄがデ
ータ番号２に与えられ、さらに、分割ブロック数ｋ及び
分割平文長［ｌｏｇ2ｎ］がデータ番号３及び４に与え
られる。また、認証文Ｍは、データ番号５＋２ｋに与え
られ、データ番号５から４＋２ｋまで及び６＋２ｋは作
業領域として使用され、処理結果の暗号化認証子ブロッ
クはデータ番号７＋２ｋから６＋３ｋに格納される。
【０１８９】図１２によれば、まず、データ番号５＋２
ｋの認証文Ｍに対して、ハッシュ関数ｈでハッシュ化
し、その結果である認証子ｈ（Ｍ）をデータ番号６＋２
ｋに格納する（ステップＳ６０１）。次いで、データ番
号６＋２ｋの認証子に対して、法ｎのもとでｄ乗演算に
よる暗号化処理を行い、その結果であるｎ進表現された
認証子の最下位桁であるｈ（Ｃ）0 をデータ番号７＋２
ｋに格納する（ステップＳ６０３）。
【０１９０】次いで、ｎ進表現された認証子を法ｎk の
もとでｅ乗した式を展開したときのｎ0 の項の係数であ
るＫ0 を公開鍵２ｅを用いてＫ0 ＝ｈ（Ｃ）0 e により
求め、データ番号５に格納する（ステップＳ６０５）。
次いでｎ進表現された上位桁を順次求めるための反復パ
ラメータｉを１に初期設定する（ステップＳ６０７）。
【０１９１】次いで、反復パラメータｉについて、Ｍ0
，Ｍ1 ，…，Ｍi-1 を変数とする多項式関数であるＫi
-1 を、前のステップまでに求められたＭ0 ，Ｍ1 ，
…，Ｍi-1 を用いて計算し、その値（整数値）をデータ
番号４＋ｉに格納し、同様に、Ｍ0 ，Ｍ1 ，…，Ｍi-1
を変数とする多項式関数であるＫ'iを、前のステップま
でに求められたＭ0 ，Ｍ1 ，…，Ｍi-1 を用いて計算
し、その値（整数値）をデータ番号５＋ｋ＋ｉに格納す
る（ステップＳ６０８）。
【０１９２】次いで、データ番号６＋２ｋの認証子ｈ
（Ｍ）と、データ番号５から５＋ｉ−１のＫj （０≦ｊ
≦ｉ−１）と、データ番号５＋ｋ＋ｉのＫ'iに対して、
以下のｂi を計算する（ステップＳ６０９）。
【０１９３】
【数４９】 次いで、ユークリッドの互除法により、合同式
【数５０】 ｅｈ（Ｃ）0 e-1 ｘ≡ｂi （ｍｏｄ ｎ） …(55) をみたすｘを求めることにより、ｈ（Ｃ）i を暗号化
し、その結果をデータ番号７＋２ｋ＋ｉに格納する（ス
テップＳ６１１）。
【０１９４】次いで、反復終了条件ｉ＝ｋ−１を判定し
（ステップＳ６１３）、成立しなければ、反復パラメー
タを１だけ増加させて（ステップＳ６１５）、ステップ
Ｓ６０９へ戻る。反復終了条件が成立すれば、データ番
号７＋２ｋから６＋３ｋまでの暗号化されたｋ個の認証
子ブロックの組とデータ番号５＋２ｋの認証文Ｍとのペ
アを送り（ステップＳ６１７）、処理を終了する。
【０１９５】図１４は、本発明に係るｎ進表現暗号をＲ
ＳＡ型公開鍵暗号に適用した場合の認証文検証処理を示
すフローチャートであり、表５は、同処理におけるメモ
リ上のデータ配置を示す表である。
【０１９６】
【表５】 表５に示すように、認証文検証処理は、公開鍵１ｎ及び
公開鍵２ｅがそれぞれデータ番号１、２に与えられ、さ
らに、分割ブロック数ｋ及び分割平文長［ｌｏｇ2ｎ］
がデータ番号３及び４に与えられる。
【０１９７】また、平文である認証文Ｍがデータ番号５
に、暗号化された認証子ブロックがデータ番号６から５
＋ｋに与えられる。データ番号５＋ｋ＋１及び５＋ｋ＋
２は、作業領域である。
【０１９８】図１４によれば、まず、送り手の公開鍵２
であるｅを利用して、データ番号６から５＋ｋまでのｋ
個の認証子ブロックに対して、それぞれの認証子ブロッ
クを一つのｎ進数のそれぞれの桁とするデータ結合を行
い、法ｎkのもとで、
【数５１】 ｈ(Ｍ)≡(ｈ(Ｃ)0 ＋ｎｈ(Ｃ)1 ＋ｎ2ｈ(Ｃ)2 ＋…＋ｎk-1ｈ(Ｃ)k-1)e …(56) 式（５６）を計算することによって、認証子１を復号化
し、その結果をデータ番号５＋ｋ＋１に格納する（ステ
ップＳ７０１）。
【０１９９】次いで、データ番号５の認証文Ｍに対し
て、ハッシュ関数ｈでハッシュ化を行い、その結果ｈ
（Ｍ）′を認証子２とし、データ番号５＋ｋ＋２に格納
する（ステップＳ７０３）。次いで、データ番号５＋ｋ
＋１の復号化認証子１ｈ（Ｍ）と、データ番号５＋ｋ＋
２のハッシュ化認証子２ｈ（Ｍ）′とを比較する（ステ
ップＳ７０５）。
【０２００】ステップＳ７０５の比較の結果、両者が一
致していれば、認証成功を出力し（ステップＳ７０
７）、一致しなければ認証失敗を出力（ステップＳ７０
９）して、処理を終了する。
【０２０１】［ラビン型暗号化通信装置］図５は、本発
明に係るＮ進表現暗号をラビン型公開鍵暗号に適用した
実施の形態を示す暗号化通信装置の構成を示すブロック
図である。
【０２０２】図５によれば、暗号化通信装置２１１は、
鍵生成処理部２１と、暗号化装置２３１と、復号化装置
２４１と通信路５１とを備えて構成されている。
【０２０３】［鍵生成処理部］鍵生成処理部２１は、図
１に示した鍵生成処理部２１と同等の鍵生成機能を有す
るものであり、その前半の機能を利用する。鍵生成処理
部２１は、秘密鍵である２個の素数ｐ，ｑを生成し、そ
の積ｎ＝ｐｑを計算し、公開鍵とする。
【０２０４】［暗号化装置］暗号化装置２３１は、平文
分割処理部２３３と、データ結合部２３５と、暗号化処
理部２３７とを備えて構成され、平文Ｍを暗号化した暗
号文Ｃを生成し、通信路５１を介して復号化装置２４１
へ送信するものである。
【０２０５】平文分割処理部２３３は、ｎの剰余類の範
囲内の大きさのｋ個のブロックに分割された分割平文
（Ｍ0 ，Ｍ1 ，…，Ｍk-1 ）を生成し、データ結合処理
部２３５へ引き渡す。
【０２０６】データ結合処理部２３５は、次に示す式
（５７）のように、１つのｎ進数Ｍ（ｎ）の各桁の値が
分割平文の各ブロックＭi （０≦ｉ≦ｋ−１）となるよ
うに、それぞれのブロックのデータを結合したｎ進数表
現を行い、このｎ進数Ｍ（ｎ）を暗号化処理部２３７へ
引き渡す。
【０２０７】
【数５２】 Ｍ（ｎ）＝Ｍ0 ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1 Ｍk-1 …(57) 暗号化処理部２３７は、データ結合処理部２３５から受
けたｎ進数Ｍ（ｎ）を受け手の公開鍵であるｎを用い
て、
【数５３】 Ｃ≡（Ｍ（ｎ））2 （ mod ｎk ） ≡（Ｍ0 ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）2 （ mod ｎk ） …(58) 式（５８）によって暗号化を行ない、通信路５１を介し
て復号化装置２４１に対して送信する。
【０２０８】［復号化装置］一方、復号化装置２４１
は、最下位桁復号化処理部２４３と、上位桁復号化処理
部２４５と、データ連結処理部２４７とを備えて構成さ
れ、通信路５１を介して受信した暗号文Ｃから、分割平
文（Ｍ0 ，Ｍ1 ，…，Ｍk-1 ）を復号化し、これらを連
結して、元の平文Ｍを復元するものである。
【０２０９】最下位桁復号化処理部２４３は、自らの秘
密鍵であるｐ，ｑ（ｎ＝ｐｑ）を用いて、
【数５４】 ｘ2 ≡Ｃ（ｍｏｄ ｐ），ｘ2 ≡Ｃ（ｍｏｄ ｑ） …(59) 連立合同式（５９）を解くことにより、Ｍ0 を復号化す
る。これには、標準的な方法を利用する。
【０２１０】上位桁復号化処理部２４５は、Ｍ0 を利用
して、ｎを法とする１次合同式を解くことにより、最下
位桁Ｍ0 を除く上位桁のブロックＭ1 ，Ｍ2 ，…，Ｍk-
1 を順次復号化し、Ｍ0 とともに、データ連結処理部２
４７へ引き渡す。
【０２１１】ここで、Ｍ1 ，…，Ｍk-1 については、以
下のように帰納的に求める。
【０２１２】
【数５５】 をみたす１次合同式の解が分割平文Ｍi である。
【０２１３】データ連結処理部２４７は、復号化された
分割平文（Ｍ0 ，Ｍ1 ，…，Ｍk-1）を統合し、原平文
Ｍへ復元する。
【０２１４】次に、この暗号化通信装置２１１の動作を
フローチャート及びメモリ上のデータ配置を示す表を参
照しながら、詳細に説明する。
【０２１５】図１５は、暗号化装置２３１の暗号化送信
処理の動作を説明するフローチャートであり、表６は、
同処理におけるメモリ上のデータ配置を示す表である。
【０２１６】
【表６】 表６に示すように、暗号化送信処理は、公開鍵ｎ、分割
平文長［ｌｏｇ2ｎ］及び平文Ｍがそれぞれデータ番号
１、３、４に与えられる。データ番号５からデータ番号
４＋ｋまでは、分割された平文ブロックを格納する作業
領域であり、分割ブロック数ｋと、暗号文ブロックＣが
この処理の結果として、データ番号２及びデータ番号４
＋ｋ＋１に得られる。なお、ここでは分割ブロック数ｋ
は、分割の結果として得られるものとしたが、最初から
定数が与えられ、この定数の分割ブロック毎に暗号化を
行うことも可能である。
【０２１７】図１５によれば、まず、データ番号４の平
文Ｍを読出し、その先頭から、それぞれ［ｌｏｇ2ｎ］
ビット長のｋ個の平文ブロックＭi （０≦ｉ≦ｋ−１）
を切り出し、各平文ブロックをデータ番号５から４＋ｋ
までに順次格納し、データ番号４には、切り出した残り
のメッセージＭ′を格納する（ステップＳ８０１）。
【０２１８】次いで、データ番号５から４＋ｋまでのｋ
個の平文ブロックに対して、ｎ進数、
【数５６】 Ｍ（ｎ）＝Ｍ0 ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1ＭK-1 …(61) を求める（ステップＳ８０３）。
【０２１９】次いで、データ番号１の公開鍵ｎを用い
て、Ｃ≡｛Ｍ（ｎ）｝2 （ mod ｎk）を求め、暗号
文Ｃとして、データ番号４＋ｋ＋１に格納する（ステッ
プＳ８０５）。次いで、データ番号４＋ｋ＋１の暗号文
を送信し（ステップＳ８０７）、データ番号４にメッセ
ージが残っているか否かを調べる（ステップＳ８０
９）。メッセージが残っていれば、ステップＳ８０１へ
戻る。メッセージが残っていなければ、終了する。
【０２２０】図１６及び図１７は、復号化装置２４１の
受信復号化処理の動作を示すフローチャートであり、表
７は、同処理におけるメモリ上のデータ配置を示す表で
ある。
【０２２１】
【表７】 表７に示すように、受信復号化処理は、公開鍵ｎ及び秘
密鍵ｐ，ｑがそれぞれデータ番号１、２に与えられ、分
割ブロック数ｋ、分割平文長［ｌｏｇ2ｎ］、及び暗号
文Ｃがデータ番号３、４及び５に与えられる。また、デ
ータ番号６から６＋ｋ−１までは分割された平文ブロッ
クを格納する作業領域として使用され、結果の統合平文
はデータ番号６＋ｋに格納される。
【０２２２】図１６によれば、まず、データ番号５の暗
号文Ｃに対して、ｘ2≡Ｃ （ｍｏｄ ｎ）（ｎ＝ｐ
ｑ）を解くことにより、ｎ進表現された平文の最下位桁
である平文ブロックＭ0 を復号化する。すなわち、ｘ2
≡Ｃ （ｍｏｄ ｐ）およびｘ2≡Ｃ （ｍｏｄ ｑ）
の連立２次合同式を解くことにより、最下位桁Ｍ0 を復
号化し、データ番号６に格納する（ステップＳ９０
１）。
【０２２３】次いで、ｎ進表現された上位桁Ｍi （１≦
ｉ≦ｋ−１）を復号化する（このステップＳ９１１以下
の詳細は、図１７により説明する）。次いで、データ番
号６から６＋ｋ−１までの復号化されたｋ個の平文ブロ
ックを連接し、そのビット列をデータ番号６＋ｋの末尾
に連接して格納し（ステップＳ９３１）、処理を終了す
る。
【０２２４】ステップＳ９０１における連立２次合同式
の解法の一例として、ｘ2≡Ｃ （ｍｏｄ ｐ）は、最
大公約数を示す関数をＧＣＤで表すとき、
【数５７】 ＧＣＤ（ｘ(p-1)/2−１，ｘ2−Ｃ）＝ｘ−Ｍp …（62） 式（６２）を計算することにより求まり、このＭp と同
様に求めたＭq とから、
【数５８】 Ｍ0 ≡ｑ×Ｍp ＋ｐ×Ｍq （ｍｏｄ ｎ） …（63） 式（６３）を計算することにより求められる。なお、こ
こに示した解法は、あくまで一例を示すものであり、ス
テップＳ９０１の連立２次合同式の解法は他の方法が多
く存在する。
【０２２５】図１７は、ｎ進表現された上位桁Ｍi （１
≦ｉ≦ｋ−１）の復号化を詳細に説明するフローチャー
トである。まず、ｎ進表現された上位桁を順次求めるた
めの反復パラメータｉを１に初期設定する（ステップＳ
９１３）。
【０２２６】次いで、それぞれ０以上ｉ−１以下の２つ
のパラメータｌ、ｍであって、かつｌ＋ｍがｉ以下の範
囲について、Ｍl Ｍm ｎl+mの総和であるＬをｎi+1 を
法として計算する（ステップＳ９１５）。次いで、ｂｉ
≡（Ｃ−Ｌ（ｍｏｄ ｎi+1））／ｎi （ｍｏｄ
ｎ）を求める（ステップＳ９１７）。
【０２２７】次いで、２Ｍ0 ｘ≡ｂi （ｍｏｄ ｎ）
を解く（ステップＳ９１９）ことにより、ｉ番目の桁の
値Ｍi を確定し、データ番号６＋ｉに格納する（ステッ
プＳ９１２）。次いで、反復終了条件ｉ＝ｋ−１を判定
し（ステップＳ９２３）、成立しなければ、反復パラメ
ータを１だけ増加させて（ステップＳ９２５）、ステッ
プＳ９１５へ戻る。反復終了条件が成立すれば、処理を
終了する。
【０２２８】［ラビン型暗号化通信装置の変形例］次
に、図２２は、本発明に係るＮ進表現暗号をラビン型公
開鍵暗号に適用した実施の形態の変形例を示す暗号化通
信装置の構成を示すブロック図である。本変形例では、
複数の平文ブロックＭの先頭に乱数ブロックＲを配置
し、Ｍ0 をＲで置き換えた例を説明する。これは、平文
Ｍに代えて、乱数ブロックＲと平文Ｍとを連接したＲ‖
Ｍを暗号化の対象とするとも考えられる。
【０２２９】図２２によれば、暗号化通信装置２１２
は、鍵生成処理部２１と、暗号化装置２３０と、復号化
装置２４１と通信路５１とを備えて構成されていて、暗
号化装置２３０以外の構成要素は、図５と同様であるの
で詳細な説明は省略する。
【０２３０】［暗号化装置］暗号化装置２３０は、乱数
発生部２３２と、平文分割処理部２３４と、データ結合
部２３５と、暗号化処理部２３７とを備えて構成され、
乱数Ｒと平文Ｍとを連接したＲ‖Ｍを暗号化した暗号文
Ｃを生成し、通信路５１を介して復号化装置２４１へ送
信するものである。
【０２３１】乱数発生部２３２は、分割平文長［ｌｏｇ
2 Ｎ］ビットに等しい長さの乱数Ｒを発生する。この乱
数は、数学的または論理的に発生される再現性のある擬
似乱数であってもよいし、再現性のない乱数であっても
良い。また、乱数Ｒは、復号化装置２４１と共有する必
要がないので、ホワイトノイズ等を利用した数学的、論
理的に再現性のない乱数発生手段を用いても良い。さら
に、一回の暗号化通信毎に新たな乱数Ｒを生成して使用
することが暗号の強度を高める点で好ましい。複数の通
信相手に対して同じＭを送る同報通信の場合にも、通信
相手毎に乱数Ｒの値を変えることにより、同報通信攻撃
に対する暗号強度が高まる。
【０２３２】平文分割処理部２３４は、入力される平文
Ｍの先頭に乱数発生部２３２から与えられる乱数Ｒを連
接してＲ‖Ｍとしたものを、ｎの剰余類の範囲内の大き
さのｋ個のブロックに分割された分割平文（Ｒ ，Ｍ1
，…，Ｍk-1 ）を生成し、データ結合処理部２３５へ
引き渡す。この結果、本変形例では、図５に示した実施
形態の分割平文の先頭ブロックＭ0 に代えて、乱数Ｒが
配置されたこととなる。これは、平文Ｍのビット列の先
頭に［ｌｏｇ2 Ｎ］ビットの乱数Ｒを配置してＲ‖Ｍと
し、そのメッセージを改めてＭとしたと考えても良い。
【０２３３】データ結合処理部２３５は、次に示す式
（６４）のように、１つのｎ進数Ｍ（ｎ）の各桁の値が
分割平文の各ブロックＭi （０≦ｉ≦ｋ−１）となるよ
うに、それぞれのブロックのデータを結合したｎ進数表
現を行い、このｎ進数Ｍ（ｎ）を暗号化処理部２３７へ
引き渡す。
【０２３４】
【数５９】 Ｍ（ｎ）＝Ｒ＋ｎＭ1 ＋ｎ2Ｍ2 ＋…＋ｎk-1 Ｍk-1 …(64) 暗号化処理部２３７は、データ結合処理部２３５から受
けたｎ進数Ｍ（ｎ）を受け手の公開鍵であるｎを用い
て、
【数６０】 Ｃ≡（Ｍ（ｎ））2 （ mod ｎk ） ≡（Ｒ＋ｎＭ1 ＋…＋ｎk-1 Ｍk-1 ）2 （ mod ｎk ） …(65) 式（６５）によって暗号化を行ない、通信路５１を介し
て復号化装置２４１に対して送信する。
【０２３５】［復号化装置］一方、復号化装置２４１
は、最下位桁復号化処理部２４３と、上位桁復号化処理
部２４５と、データ連結処理部２４７とを備えて構成さ
れ、通信路５１を介して受信した暗号文Ｃから、分割平
文（Ｒ，Ｍ1 ，…，Ｍk-1 ）を復号化し、これらを連結
して、元の平文Ｍを復元するものである。
【０２３６】最下位桁復号化処理部２４３は、自らの秘
密鍵であるｐ，ｑ（ｎ＝ｐｑ）を用いて、
【数６１】 ｘ2 ≡Ｃ（ｍｏｄ ｐ），ｘ2 ≡Ｃ（ｍｏｄ ｑ） …(66) 連立合同式（６６）を解くことにより、最下位桁である
Ｒを復号化する。これには、標準的な方法を利用する。
【０２３７】上位桁復号化処理部２４５は、Ｒを利用し
て、ｎを法とする１次合同式を解くことにより、最下位
桁Ｒを除く上位桁のブロックＭ1 ，Ｍ2 ，…，Ｍk-1 を
順次復号化し、データ連結処理部２４７へ引き渡す。
【０２３８】ここで、Ｍ1 ，…，Ｍk-1 については、以
下のように帰納的に求める。
【０２３９】
【数６２】 （数５５）と同様の式をみたす１次合同式を解き、その
解をｒk とする。すると、Ｍk ＝Ｍk-1 ＋ｒkｎk の関
係式からＭ1 ，…，Ｍk-1 が順次求まる。
【０２４０】データ連結処理部２４７は、復号化された
分割平文（Ｍ1 ，…，Ｍk-1 ）を統合し、原平文Ｍへ復
元する。乱数Ｒはメッセージとしては必要ないものであ
り、上位桁復号化処理部４５による復号に利用されたの
ち、廃棄しても差し支えない。
【０２４１】［Ｎ進表現暗号をラビン型暗号に適用した
場合の具体例］次に、本発明に係るＮ進表現暗号をラビ
ン型暗号に適用した場合の実施の形態を具体的な数値を
用いて説明する。
【０２４２】［鍵生成処理部］２個の素数ｐ＝８６３，
ｑ＝７３３（秘密鍵）を生成し、その積ｎ＝632579（公
開鍵）を決定する。ｋ＝２とする。
【０２４３】［平文分割処理部］平文Ｍ＝1234567890に
対して、ｎの剰余類の範囲内の分割平文（Ｍ0 ，Ｍ1 ）
＝（12345，67890）を生成する。
【０２４４】［暗号化処理部］以下に示す式（６８）に
よって暗号化を行い、通信路を介して復号化装置へ送信
する。
【０２４５】
【数６３】 Ｃ≡（12345＋632579×67890）2 （ｍｏｄ 6325792 ）＝317915175516 …（68）
【０２４６】［最下位桁復号化処理部］最下位桁復号化
処理部は、自らの秘密鍵であるｐ＝８６３，ｑ＝７３３
に対し、
【数６４】 ｘ2 ≡Ｃ（ｍｏｄ ｐ），ｘ2 ≡Ｃ（ｍｏｄ ｑ） …（69） ２次合同式（６９）を解き、最下位桁であるＭ0 ＝1234
5を得る。
【０２４７】［上位桁復号化処理部］次に、ｎ＝632579
を法とする
【数６５】 24690ｘ≡502329 (ｍｏｄ 632579） …（70） １次合同式（７０）を解くことにより、上位桁であるＭ
1 ＝67890を得る。
【０２４８】［データ連結処理部］復号化された分割平
文（Ｍ0 ，Ｍ1 ）＝（12345，67890）を統合し、原平文
Ｍ＝1234567890へ復元する。
【０２４９】［認証装置］次に、本発明に係るｎ進表現
暗号をラビン型公開鍵暗号に適用した実施の形態を示す
認証装置及び認証方法を説明する。図６は、本発明に係
るｎ進表現暗号をラビン型公開鍵暗号に適用した実施の
形態を示す認証装置の構成を示すブロック図である。図
６によれば、認証装置３１１は、鍵生成処理部２１と、
認証文生成装置３３１と、認証文検証３４１と通信路５
１とを備えて構成されている。
【０２５０】本発明のｎ進表現を用いた暗号方式を用
い、認証を行ないたい者が、自らの秘密鍵により認証文
の暗号化を行なって生成した認証子を受け手に送る方式
による認証装置を構成することができる。以下に、構成
方法を記述する。
【０２５１】［鍵生成処理部］鍵生成処理部２１は、２
個の素数ｐ，ｑ（秘密鍵１）を生成し、その積ｎ＝ｐｑ
（公開鍵１）を決定する。この鍵生成処理部２１の動作
は、図１の暗号化通信装置１１の鍵生成処理部２１の前
半の動作と全く同じである。
【０２５２】［認証文生成装置］認証文生成装置３３１
は、認証文ハッシュ化処理部３３３と、最下位桁暗号化
処理部３３５と、上位桁暗号化処理部３３７と、データ
連結処理部３３９とを備えて構成されている。
【０２５３】［認証文ハッシュ化処理部］認証文ハッシ
ュ化処理部３３３は、認証文Ｍに対して、ハッシュ関数
ｈによりハッシュ化を行い、認証子ｈ（Ｍ）を得る。た
だし、０≦ｈ（Ｍ）＜ｎk とする。
【０２５４】［最下位桁暗号化処理部］最下位桁暗号化
処理部３３５は、送り手の公開鍵であるｎと秘密鍵であ
るｐ，ｑを用いて、
【数６６】 ｘ2 ≡ｈ（Ｍ）（ｍｏｄ ｐ），ｘ2 ≡ｈ（Ｍ）（ｍｏｄ ｑ） …（71） 連立２次合同式（７１）の解である暗号化認証子の最下
位桁であるｈ（Ｃ）0 を計算する。
【０２５５】［上位桁暗号化処理部］上位桁暗号化処理
部３３７は、図５の復号化装置２４１における復号化の
ときと同じ１次合同式を解くことにより、ｈ（Ｃ）1 ，
ｈ（Ｃ）2 ，…，ｈ（Ｃ）k-1 を計算し、暗号化された
認証子１（ｈ（Ｃ）0 ，ｈ（Ｃ）1 ，…，ｈ（Ｃ）k-1
）を求める。認証子１と認証文Ｍの組を通信路５１を
介して認証文検証装置に送る。
【０２５６】ここで、方程式の解が存在しない場合は、
Ｍ＝Ｍ＋ｒ，（ｒはある数）とし認証文ハッシュ化処理
に戻る。
【０２５７】［データ連結処理部］データ連結処理部３
３９は、ｎ進表現された認証子の最下位桁と上位桁とを
連結し、暗号化された認証子１（ｈ（Ｃ）0 ，ｈ（Ｃ）
1 ，…，ｈ（Ｃ）k-1 ）を生成する。そして、認証子１
と認証文Ｍの組を通信路５１を介して受け手である認証
文検証装置３４１に送る。
【０２５８】［認証文検証装置］認証文検証装置３４１
は、データ結合処理部３４３と、認証子復号化処理部３
４５と、認証文ハッシュ化処理部３４７と、照合判定部
３４９とを備えて構成されている。
【０２５９】［データ結合処理部］データ結合処理部３
４３は、受信した暗号化認証子の各ブロックをｎ進数の
各桁を表す数値としてデータ結合し、ｎ進数表現された
（ｈ（Ｃ）0 ＋ｎｈ（Ｃ）1 ＋…＋ｎk-1 ｈ（Ｃ）k-1
）を生成する。
【０２６０】［認証子復号化処理部］認証子復号化処理
部３４５は、送り手の公開鍵であるｎを利用して、
【数６７】 ｈ（Ｍ）≡（ｈ（Ｃ）0 ＋ｎｈ（Ｃ）1 ＋… ＋ｎk-1 ｈ（Ｃ）k-1 ）2 （ｍｏｄ ｎk ） …(72) を計算することによって、認証子１を復号化する。
【０２６１】［認証文ハッシュ化処理部］認証文ハッシ
ュ化処理部３４７は、ハッシュ関数ｈを用い、認証文Ｍ
のハッシュ化ｈ（Ｍ）を行い、認証子２とする。
【０２６２】［照合判定部］照合判定部３４９は、認証
子１と認証子２とを比較照合し、これらが一致していれ
ば、認証は成功し、一致していなければ認証は不成功と
して、認証文の正当性を判断する。
【０２６３】次に、この認証装置３１１の動作をフロー
チャート及びメモリ上のデータ配置を示す表を参照しな
がら、詳細に説明する。
【０２６４】図１８及び１９は、本発明に係るｎ進表現
暗号をラビン型公開鍵暗号に適用した場合の認証文生成
処理を示すフローチャートであり、表８は、同処理にお
けるメモリ上のデータ配置を示す表である。
【０２６５】
【表８】 表８に示すように、認証文生成処理は、公開鍵ｎ及び秘
密鍵ｐ，ｑがそれぞれデータ番号１、２に与えられ、分
割平文長［ｌｏｇ2ｎ］及び認証文Ｍがデータ番号４及
び５に与えられる。また、データ番号３には、認証子を
分割したブロック数ｋが格納され、データ番号６には、
ハッシュ化された認証子ｈ（Ｍ）を格納するための作業
領域として使用され、データ番号７から６＋ｋまでは、
生成された暗号化認証子ブロックが格納される。
【０２６６】図１８によれば、まず、データ番号５の認
証文Ｍに対して、ハッシュ関数ｈでハッシュ化し、その
結果である認証子ｈ（Ｍ）をデータ番号６に格納する
（ステップＳ１００１）。次いで、データ番号６の認証
子ｈ（Ｍ）に対して、分割平文長［ｌｏｇ2ｎ］で分割
したブロック数ｋを求め、データ番号３に格納する（ス
テップＳ１００３）。
【０２６７】次いで、データ番号６の認証子ｈ（Ｍ）に
対して、ｘ2≡ｈ（Ｍ） （ｍｏｄｎ）（ｎ＝ｐｑ）を
解くことにより、ｎ進表現された認証子の最下位桁であ
る認証子ブロックｈ（Ｍ）0 を暗号化する。すなわち、
ｘ2≡ｈ（Ｍ） （ｍｏｄｐ）およびｘ2≡ｈ（Ｍ）
（ｍｏｄ ｑ）の連立２次合同式を解くことにより、最
下位桁ｈ（Ｃ）0 を暗号化し、データ番号７に格納する
（ステップＳ１００５）。
【０２６８】次いで、ｎ進表現された上位桁ｈ（Ｃ）i
（１≦ｉ≦ｋ−１）を暗号化する（このステップＳ１０
１１以下の詳細は、図１９により説明する）。次いで、
データ番号７から７＋ｋ−１までの暗号化されたｋ個の
認証子ブロックと、データ番号５の認証文Ｍとのペアを
送信して（ステップＳ１０３１）、処理を終了する。
【０２６９】ステップＳ１００５における連立２次合同
式の解法の一例として、ｘ2≡ｈ（Ｍ） （ｍｏｄ
ｐ）は、最大公約数をＧＣＤで表すとき、
【数６８】 ＧＣＤ（ｘ(p-1)/2−１，ｘ2−ｈ（Ｍ））＝ｘ−ｈ（Ｃ）p …（73） 式（７３）を計算することにより求まり、このｈ（Ｃ）
p と同様に求めたｈ（Ｃ）q とから、
【数６９】 ｈ（Ｃ）0 ≡ｑ×ｈ（Ｃ）p ＋ｐ×ｈ（Ｃ）q （ｍｏｄ ｎ） …（74） 式（７４）を計算することにより求められる。なお、こ
こに示した解法は、あくまで一例を示すものであり、ス
テップＳ１００５の連立２次合同式の解法は他の方法が
多く存在する。
【０２７０】図１９は、ｎ進表現された上位桁ｈ（Ｃ）
i （１≦ｉ≦ｋ−１）の暗号化を詳細に説明するフロー
チャートである。まず、ｎ進表現された上位桁を順次求
めるための反復パラメータｉを１に初期設定する（ステ
ップＳ１０１３）。
【０２７１】次いで、それぞれ０以上ｉ−１以下の２つ
のパラメータｌ、ｍであって、かつｌ＋ｍがｉ以下の範
囲について、ｈ（Ｃ）l ｈ（Ｃ）m ｎl+m のｎi+1 を法
とする総和であるＬを計算する（ステップＳ１０１
５）。次いで、ｂｉ≡（ｈ（Ｍ）−Ｌ（ｍｏｄ
ｎi+1 ））／ｎi （ｍｏｄ ｎ）を求める（ステップ
Ｓ１０１７）。
【０２７２】次いで、２ｈ（Ｃ）0 ｘ≡ｂi （ｍｏｄ
ｎ）を解く（ステップＳ１０１９）ことにより、ｉ番
目の桁の値ｈ（Ｃ）i を確定し、データ番号７＋ｉに格
納する（ステップＳ１０１２）。次いで、反復終了条件
ｉ＝ｋ−１を判定し（ステップＳ１０２３）、成立しな
ければ、反復パラメータを１だけ増加させて（ステップ
Ｓ１０２５）、ステップＳ１０１５へ戻る。反復終了条
件が成立すれば、処理を終了する。
【０２７３】図２０は、本発明に係るｎ進表現暗号をラ
ビン型公開鍵暗号に適用した場合の認証文検証処理を示
すフローチャートであり、表９は、同処理におけるメモ
リ上のデータ配置を示す表である。
【０２７４】
【表９】 表９に示すように、認証文検証処理は、公開鍵ｎ、分割
ブロック数ｋ及び分割平文長［ｌｏｇ2ｎ］がデータ番
号１、３及び４に与えられる。
【０２７５】また、平文である認証文Ｍがデータ番号５
に、暗号化された認証子ブロックがデータ番号６から５
＋ｋに与えられる。データ番号５＋ｋ＋１及び５＋ｋ＋
２は、作業領域である。データ番号２は使用されない。
【０２７６】図２０によれば、まず、送り手の公開鍵で
あるｎを利用して、データ番号６から５＋ｋまでのｋ個
の認証子ブロックに対して、それぞれの認証子ブロック
を一つのｎ進数のそれぞれの桁とするデータ結合を行
い、法ｎkのもとで、
【数７０】 ｈ(Ｍ)≡(ｈ(Ｃ)0 ＋ｎｈ(Ｃ)1 ＋ｎ2ｈ(Ｃ)2 ＋…＋ｎk-1ｈ(Ｃ)k-1)2 …（75） を計算することによって、認証子１を復号化し、その結
果をデータ番号５＋ｋ＋１に格納する（ステップＳ１１
０１）。
【０２７７】次いで、データ番号５の認証文Ｍに対し
て、ハッシュ関数ｈでハッシュ化を行い、その結果ｈ
（Ｍ）′を認証子２とし、データ番号５＋ｋ＋２に格納
する（ステップＳ１１０３）。次いで、データ番号５＋
ｋ＋１の復号化認証子１ｈ（Ｍ）と、データ番号５＋ｋ
＋２のハッシュ化認証子２ｈ（Ｍ）′とを比較する（ス
テップＳ１１０５）。
【０２７８】ステップＳ１１０５の比較の結果、両者が
一致していれば、認証成功を出力し（ステップＳ１１０
７）、一致しなければ認証失敗を出力（ステップＳ１１
０９）して、処理を終了する。
【０２７９】［係数テーブルを使用しない復号化方法の
原理説明］次に、本発明に係るＮ進表現暗号の係数テー
ブルを使用しない復号化方法の原理を説明する。この復
号化方法は、最下位桁Ｍ0 の値を使用して、同一の写像
または同一の計算式により再帰的に上位桁Ｍi （１≦ｉ
≦ｋ−１）を復号するものであり、ＲＳＡ型Ｎ進表現暗
号を用いて復号原理を説明するが、ラビン型Ｎ進表現暗
号の場合には、ｅ＝２とおくことにより、同様の式で上
位桁を復号することができる。なお、最下位桁Ｍ0 の復
号化は、前記の実施形態と同様であるので説明を省略す
る。
【０２８０】いま、（ｉ−１）桁目のＭi-1 まで復号化
されたときに、ｉ桁目のＭi を復号化することを考え
る。
【０２８１】既に復号化されたＭ0 からＭi-1 までのｉ
個の平文ブロックをｎ進数として表現したものをＡi-1
とすれば、
【数７１】 Ａi-1 ＝Ｍ0 ＋ｎＭ1 ＋ｎ2 Ｍ2 ＋…＋ｎi-1 Ｍi-1 …（76） であるから、Ａi-1 を利用して受信暗号文Ｃを表現する
と、
【数７２】 Ｃ≡（Ｍ0＋ｎＭ1＋…＋ｎk-1Ｍk-1 ）e （mod ｎk ） ≡（Ａi-1＋ｎiＭi＋ｎi+1Ｍi+1＋…＋ｎk-1 Ｍk-1 ）e （mod ｎk ） …（77） となる。
【０２８２】ここで、Ｍi の復号に不要である（ｉ＋
１）桁目以上の桁であるＭi+1 以降の平文ブロックの影
響を除去するため、両辺をｎi+1 で除した剰余を考え
る。
【０２８３】
【数７３】 Ｃ ≡Ａi-1e ＋ｅＡi-1e-1 ｎi Ｍi （mod ｎi+1 ） …（78） 移項して、
【数７４】 ｅＡi-1e-1 ｎi Ｍi ≡Ｃ−Ａi-1e （mod ｎi+1 ） …（79） 両辺をｎi で除算すると、
【数７５】 ｅＡi-1e-1 Ｍi ≡（Ｃ−Ａi-1e （mod ｎi+1 ））／ｎi （mod ｎ ） …(80) ゆえに、合同式
【数７６】 ｅＡi-1e-1 ｘ ≡（Ｃ−Ａi-1e （mod ｎi+1 ））／ｎi （mod ｎ ） …(81) をみたすｘを求めることにより、Ｍi を復号化すること
ができる。
【０２８４】このＭi を順次下位の桁から上位の桁へ、
再帰的に同じ手順で求めるプログラムを次に示す。な
お、記号「：＝０」は、右辺の定数値または計算値を左
辺に代入する代入記号であり、「ｆｏｒ」で始まる文
は、「ｂｅｇｉｎ」と「ｅｎｄ」で挟まれた実行文を繰
り返すことを指示する繰り返し制御文である。
【０２８５】
【数７７】入力：ｎ，ｅ，Ｃ，ｋ，Ｍ0 出力：Ｍ1 ，Ｍ2 ，…，Ｍk-1 Ａ-1：＝０； ｆｏｒ ｉ＝１ ｔｏ（ｋ−１）ｄｏ ｂｅｇｉｎ Ａi-1 ：＝Ａi-2 ＋ｎi-1 Ｍi-1 ； Ｆi-1 ：＝Ａi-1 e （ｍｏｄ ｎi+1 ）； Ｅi ：＝Ｃ−Ｆi-1 （ｍｏｄ ｎi+1 ）； Ｂi ：＝Ｅi ／ｎi ； Ｍi ：＝（ｅＦi-1 ）-1Ａi-1 Ｂi （ｍｏｄ ｎ）； ｅｎｄ 以上、係数テーブルを使用しない復号方法によるＲＳＡ
型Ｎ進表現暗号の上位桁の復号原理について説明した
が、ラビン型Ｎ進表現暗号の場合には、ｅ＝２と置くこ
とにより、同様の式で上位桁を復号することができる。
【０２８６】また、ＲＳＡ型およびラビン型ともに認証
文作成における上位桁暗号化は、それぞれの復号化と同
様であるので、上記上位桁復号化原理を認証文上位桁暗
号化に利用することができる。
【０２８７】［係数テーブルを使用しない復号化の実施
形態］次に、上記復号化方法を用いたＲＳＡ型Ｎ進表現
暗号の復号化装置の動作を説明する。暗号化通信装置、
暗号化装置および復号化装置の構成は、図１および図２
１と同様であり、暗号化および最下位桁Ｍ0 （または
Ｒ）の復号化までも同様である。
【０２８８】図２３は、本実施の形態におけるＲＳＡ型
Ｎ進暗号の受信復号化処理を説明するフローチャートで
あり、表１０は、同処理におけるメモリ上のデータ配置
を示す表である。
【０２８９】
【表１０】 表１０に示すように、受信復号化処理においては、デー
タ番号１に公開鍵１ｎ及び公開鍵２ｅが与えられ、デー
タ番号２に秘密鍵２ｄが与えられ、さらに、分割ブロッ
ク数ｋ及び分割平文長［ｌｏｇ2ｎ］がデータ番号３及
び４に与えられる。また、暗号文Ｃは、データ番号５に
与えられ、データ番号６から１２＋ｋ−１までは作業領
域として使用され、結果の統合平文はデータ番号１２＋
ｋに格納される。
【０２９０】図２３によれば、まず、データ番号５の暗
号文Ｃに対して、データ番号１、２の公開鍵１ｎ、秘密
鍵２ｄを使用して、（ｍｏｄ ｎ）のもとでｄ乗演算を
行い、ｎ進表現された平文の最下位桁である平文ブロッ
クＭ0 を復元し、その結果をデータ番号６に格納する
（ステップＳ１２０１）。
【０２９１】次いで、初期化変数Ａ-1 の値０をデータ
番号８に格納し（ステップＳ１２０３）、ループカウン
タｉの初期値１をデータ番号７に格納する（ステップＳ
１２０５）。
【０２９２】次いで、Ａi-1 ：＝Ａi-2 ＋ｎi-1 Ｍi-1
を計算し、データ番号９に格納する（ステップＳ１２０
７）。次いで、Ｆi-1 ：＝Ａi-1e（mod ｎi+1 ）を計算
し、データ番号１０に格納する（ステップＳ１２０
９）。次いで、Ｅi ：＝Ｃ−Ｆi-1 （ｍｏｄ ｎi+1 ）
を計算し、データ番号１１に格納する（ステップＳ１２
１１）。
【０２９３】次いで、Ｂi ：＝Ｅi ／ｎi を計算し、デ
ータ番号１２に格納する（ステップＳ１２１３）。次い
で、Ｍi ：＝（ｅＦi-1 ）-1Ａi-1 Ｂi （ｍｏｄ ｎ）
を計算し、データ番号１２＋ｉに格納する（ステップＳ
１２１５）。
【０２９４】次いで、繰り返し終了条件ｉ＝ｋ−１を判
定し（ステップＳ１２１７）、不成立ならば、データ番
号９のＡi-1 をデータ番号８のＡi-2 へ移送するととも
に、ループカウンタｉを１だけ増加させて更新し（ステ
ップＳ１２１９）、ステップＳ１２０７へ戻る。
【０２９５】繰り返し終了条件ｉ＝ｋ−１が満足されて
いれば（ステップＳ１２１７の判定がＹＥＳ）、データ
番号６，１３，…，１２＋ｋ−１の復号化されたｋ個の
平文ブロックＭ0 ，Ｍ1 ，…，Ｍk-1 を連接し、統合平
文Ｍとしてデータ番号１２＋ｋに格納する（ステップＳ
１２２１）。
【０２９６】上記の実施形態の復号化方法によれば、表
Ｅと表３とを比較すれば明らかなように、従来Ｋｉおよ
びＫ'iの記憶のために使用していた、ほぼ平文ブロック
数の２倍の数のデータ記憶領域が不要となり、記憶領域
が節約できるとともに、復号化の為のプログラムが再帰
的に計算するのでプログラムが小さくなり、またそのプ
ログラムによる計算量も少なくなり、高速の復号化を行
うことができる。
【０２９７】次に、上記復号化方法を用いたＲＳＡ型Ｎ
進表現暗号の認証文生成装置の動作を説明する。認証装
置、認証文生成装置および認証文検証装置の構成は、図
２と同様であり、最下位桁ｈ（Ｃ）0 の暗号化処理及び
認証文検証処理も同様であり、上位桁暗号化処理部のみ
が異なる。
【０２９８】図２４は、本実施の形態におけるＲＳＡ型
Ｎ進暗号の認証文生成化処理を説明するフローチャート
であり、表１１は、同処理におけるメモリ上のデータ配
置を示す表である。
【０２９９】
【表１１】 表１１に示すように、認証文生成処理においては、公開
鍵１ｎ及び公開鍵２ｅがデータ番号１に、秘密鍵２ｄが
データ番号２に与えられ、さらに、分割ブロック数ｋ及
び分割平文長［ｌｏｇ2ｎ］がデータ番号３及び４に与
えられる。また、認証文Ｍは、データ番号５に与えら
れ、データ番号６から１３＋ｋ−１まで作業領域として
使用され、処理結果の暗号化認証子ブロックはデータ番
号７およびデータ番号１４から１３＋ｋ−１に格納され
る。
【０３００】図２４によれば、まず、データ番号５の認
証文Ｍに対して、ハッシュ関数ｈでハッシュ化し、その
結果である認証子ｈ（Ｍ）をデータ番号６に格納する
（ステップＳ１３０１）。
【０３０１】次いで、データ番号６の認証子ｈ（Ｍ）に
対して、法ｎのもとで自らの秘密鍵２によるｄ乗演算に
よる暗号化処理を行い、その結果であるｎ進表現された
認証子の最下位桁であるｈ（Ｃ）0 をデータ番号７に格
納する（ステップＳ１３０３）。
【０３０２】次いで、初期化変数Ａ-1 の値０をデータ
番号９に格納し（ステップＳ１３０５）、ループカウン
タｉの初期値１をデータ番号８に格納する（ステップＳ
１３０７）。
【０３０３】次いで、Ａi-1 ：＝Ａi-2 ＋ｎi-1 ｈ
（Ｃ）i-1 を計算し、データ番号１０に格納する（ステ
ップＳ１３０９）。次いで、Ｆi-1 ：＝Ａi-1e（mod ｎ
i+1 ）を計算し、データ番号１１に格納する（ステップ
Ｓ１３１１）。次いで、Ｅi ：＝ｈ（Ｍ）−Ｆi-1 （ｍ
ｏｄ ｎi+1 ）を計算し、データ番号１２に格納する
（ステップＳ１３１３）。
【０３０４】次いで、Ｂi ：＝Ｅi ／ｎi を計算し、デ
ータ番号１３に格納する（ステップＳ１３１５）。次い
で、ｈ（Ｃ）i ：＝（ｅＦi-1 ）-1Ａi-1 Ｂi （ｍｏｄ
ｎ）を計算し、データ番号１３＋ｉに格納する（ステ
ップＳ１３１７）。
【０３０５】次いで、繰り返し終了条件ｉ＝ｋ−１を判
定し（ステップＳ１３１９）、不成立ならば、データ番
号１０のＡi-1 をデータ番号９のＡi-2 へ移送するとと
もに、ループカウンタｉを１だけ増加させて更新し（ス
テップＳ１３２１）、ステップＳ１３０９へ戻る。
【０３０６】繰り返し終了条件ｉ＝ｋ−１が満足されて
いれば（ステップＳ１３１９の判定がＹＥＳ）、データ
番号７，１４，１５，…，１３＋ｋ−１の暗号化された
ｋ個の認証子ブロックｈ（Ｃ）0 ，ｈ（Ｃ）1 ，…，ｈ
（Ｃ）k-1 と、データ番号５の認証文とのペアを送る。
【０３０７】上記の実施形態の復号化方法によれば、表
Ｆと表４とを比較すれば明らかなように、従来Ｋｉおよ
びＫ'iの記憶のために使用していた、ほぼ認証子ブロッ
ク数の２倍の数のデータ記憶領域が不要となり、記憶領
域が節約できるとともに、認証子暗号化の為のプログラ
ムが再帰的に計算するのでプログラムが小さくなり、ま
たそのプログラムによる計算量も少なくなり、高速の認
証子暗号化を行うことができる。
【０３０８】次に、係数テーブルを使用しない復号化方
法を用いたラビン型Ｎ進表現暗号の復号化装置の動作を
説明する。暗号化通信装置、暗号化装置および復号化装
置の構成は、図５および図２２と同様であり、暗号化お
よび最下位桁Ｍ0 （またはＲ）の復号化までも同様であ
る。
【０３０９】図２５は、本実施の形態におけるラビン型
Ｎ進暗号の上位桁受信復号化処理を説明するフローチャ
ートであり、表１２は、同処理におけるメモリ上のデー
タ配置を示す表である。
【０３１０】
【表１２】 表１２に示すように、受信復号化処理においては、デー
タ番号１に公開鍵ｎ、データ番号２に秘密鍵ｐ，ｑが与
えられ、さらに、分割ブロック数ｋ及び分割平文長［ｌ
ｏｇ2ｎ］がデータ番号３及び４に与えられる。また、
暗号文Ｃは、データ番号５に与えられ、データ番号６か
ら１２＋ｋ−１までは作業領域として使用され、結果の
統合平文はデータ番号１２＋ｋに格納される。
【０３１１】まず、図１６のステップＳ９０１に示した
処理により、データ番号５の暗号文Ｃに対して、データ
番号１、２の公開鍵ｎ、秘密鍵ｐ，ｑを使用して、ｎ進
表現された平文の最下位桁である平文ブロックＭ0 を復
元し、その結果がデータ番号６に格納される。
【０３１２】次いで、図２５によれば、初期化変数Ａ-1
の値０をデータ番号８に格納し（ステップＳ１４０
３）、ループカウンタｉの初期値１をデータ番号７に格
納する（ステップＳ１４０５）。
【０３１３】次いで、Ａi-1 ：＝Ａi-2 ＋ｎi-1 Ｍi-1
を計算し、データ番号９に格納する（ステップＳ１４０
７）。次いで、Ｆi-1 ：＝Ａi-12（mod ｎi+1 ）を計算
し、データ番号１０に格納する（ステップＳ１４０
９）。次いで、Ｅi ：＝Ｃ−Ｆi-1 （ｍｏｄ ｎi+1 ）
を計算し、データ番号１１に格納する（ステップＳ１４
１１）。
【０３１４】次いで、Ｂi ：＝Ｅi ／ｎi を計算し、デ
ータ番号１２に格納する（ステップＳ１４１３）。次い
で、Ｍi ：＝（２Ｆi-1 ）-1Ａi-1 Ｂi （ｍｏｄ ｎ）
を計算し、データ番号１２＋ｉに格納する（ステップＳ
１４１５）。
【０３１５】次いで、繰り返し終了条件ｉ＝ｋ−１を判
定し（ステップＳ１４１７）、不成立ならば、データ番
号９のＡi-1 をデータ番号８のＡi-2 へ移送するととも
に、ループカウンタｉを１だけ増加させて更新し（ステ
ップＳ１４１９）、ステップＳ１４０７へ戻る。
【０３１６】繰り返し終了条件ｉ＝ｋ−１が満足されて
いれば（ステップＳ１４１７の判定がＹＥＳ）、Ｍi の
復号化を終了する。この後、図１６のステップＳ９３１
と同様の処理を行い、、データ番号６，１３，…，１２
＋ｋ−１の復号化されたｋ個の平文ブロックＭ0 ，Ｍ1
，…，Ｍk-1 を連接し、統合平文Ｍとしてデータ番号
１２＋ｋに格納する。
【０３１７】上記の実施形態の復号化方法によれば、復
号化の為のプログラムが再帰的に計算するのでプログラ
ムが小さくなり、またそのプログラムによる計算量も少
なくなり、高速の復号化を行うことができる。
【０３１８】次に、上記復号化方法を用いたラビン型Ｎ
進表現暗号の認証文生成装置の動作を説明する。認証装
置、認証文生成装置および認証文検証装置の構成は、図
２と同様であり、最下位桁ｈ（Ｃ）0 の暗号化処理及び
認証文検証処理も同様であり、上位桁暗号化処理部のみ
が異なる。
【０３１９】図２６は、本実施の形態におけるラビン型
Ｎ進暗号の認証文生成化処理を説明するフローチャート
であり、表１３は、同処理におけるメモリ上のデータ配
置を示す表である。
【０３２０】
【表１３】 表１３に示すように、認証文生成処理においては、公開
鍵ｎがデータ番号１に与えられ、さらに、分割平文長
［ｌｏｇ2ｎ］がデータ番号４に与えられる。また、認
証文Ｍは、データ番号５に与えられ、データ番号６から
１３＋ｋ−１まで作業領域として使用され、処理結果の
暗号化認証子ブロックはデータ番号７およびデータ番号
１４から１３＋ｋ−１に格納される。
【０３２１】まず、図１８のステップＳ１００１からＳ
１００５に記載の処理手順により、データ番号５の認証
文Ｍに対して、ハッシュ関数ｈでハッシュ化し、その結
果である認証子ｈ（Ｍ）をデータ番号６に格納し、デー
タ番号６の認証子ｈ（Ｍ）を分割平文長［ｌｏｇ2ｎ］
で分割したブロック数ｋをデータ番号３に格納し、デー
タ番号６の認証子ｈ（Ｍ）に対して、ｘ2 ＝ｈ（Ｍ）
（mod ｐ），ｘ2 ＝ｈ（Ｍ）（mod ｑ）の連立２次合同
式を解くことにより、ｎ進表現された認証子の最下位桁
であるｈ（Ｍ）0 を求め、データ番号７に格納する。
【０３２２】次いで、図２６に記載の認証子上位桁暗号
化が行われる。図２６によれば、初期化変数Ａ-1 の値
０をデータ番号９に格納し（ステップＳ１５０３）、ル
ープカウンタｉの初期値１をデータ番号８に格納する
（ステップＳ１５０５）。
【０３２３】次いで、Ａi-1 ：＝Ａi-2 ＋ｎi-1 ｈ
（Ｃ）i-1 を計算し、データ番号１０に格納する（ステ
ップＳ１５０７）。次いで、Ｆi-1 ：＝Ａi-12（mod ｎ
i+1 ）を計算し、データ番号１１に格納する（ステップ
Ｓ１５０９）。次いで、Ｅi ：＝ｈ（Ｍ）−Ｆi-1 （ｍ
ｏｄ ｎi+1 ）を計算し、データ番号１２に格納する
（ステップＳ１５１１）。
【０３２４】次いで、Ｂi ：＝Ｅi ／ｎi を計算し、デ
ータ番号１３に格納する（ステップＳ１５１３）。次い
で、ｈ（Ｃ）i ：＝（２Ｆi-1 ）-1Ａi-1 Ｂi （ｍｏｄ
ｎ）を計算し、データ番号１３＋ｉに格納する（ステ
ップＳ１５１５）。
【０３２５】次いで、繰り返し終了条件ｉ＝ｋ−１を判
定し（ステップＳ１５１７）、不成立ならば、データ番
号１０のＡi-1 をデータ番号９のＡi-2 へ移送するとと
もに、ループカウンタｉを１だけ増加させて更新し（ス
テップＳ１５１９）、ステップＳ１５０７へ戻る。
【０３２６】繰り返し終了条件ｉ＝ｋ−１が満足されて
いれば（ステップＳ１５１７の判定がＹＥＳ）、認証子
上位桁の暗号化を終了する。この後、データ番号７，１
４，１５，…，１３＋ｋ−１の暗号化されたｋ個の認証
子ブロックｈ（Ｃ）0 ，ｈ（Ｃ）1 ，…，ｈ（Ｃ）k-1
と、データ番号５の認証文Ｍとのペアを送る。
【０３２７】上記の実施形態の認証文生成方法によれ
ば、認証子暗号化の為のプログラムが再帰的に計算する
のでプログラムが小さくなり、またそのプログラムによ
る計算量も少なくなり、高速の認証子暗号化を行うこと
ができる。
【０３２８】［ｎ進表現暗号のＲＳＡ型とラビン型との
比較］次に、本発明に係るｎ進表現を用いたＲＳＡ暗号
とラビン暗号の違いを、表１４を参照して、鍵生成・暗
号化・復号化の三点から述べる。
【０３２９】
【表１４】 ［鍵に関する比較］ｎ進表現を用いたＲＳＡ型暗号と同
ラビン型暗号では鍵の数が異なる。これは、本発明を適
用する対象の基礎となる暗号方式そのものを反映してお
り、ＲＳＡ型では、公開鍵ｎ，ｅと、秘密鍵ｄとを使用
するのに対し、ラビン型では、公開鍵ｎと秘密鍵ｐ，ｑ
を使用する。
【０３３０】ここで、ｎ＝ｐｑであり、ｅｄ≡１（ｍｏ
ｄ Ｌ），Ｌ＝ＬＣＭ（ｐ−１，ｑ−１）とする。
【０３３１】［暗号化に関する比較］それぞれの暗号化
関数とその特徴は、次のとおりである。
【０３３２】ＲＳＡ型暗号では、公開鍵ｎ，ｅを使用
し、暗号化関数、Ｃ≡Ｍe （ｍｏｄｎk）により暗号化
を行う。一方、ラビン型暗号は、公開鍵ｎを使用し、暗
号化関数、Ｃ≡Ｍ2 （ｍｏｄ ｎk）により暗号化を行
う。べき乗計算により暗号化を行うＲＳＡ型暗号は、２
乗計算により暗号化を行うラビン型暗号に比べて、暗号
化速度は低くなる。
【０３３３】ここで、ｎは公開鍵であり、ＲＳＡ暗号・
ラビン暗号の両方に使える。ｅはＲＳＡ暗号のみ必要な
鍵である。
【０３３４】［復号化に関する比較］それぞれの復号化
の関数とその特徴は、次のとおりである。
【０３３５】ＲＳＡ型暗号は、公開鍵ｎと秘密鍵ｄとを
用いて、復号化関数、Ｍ≡Ｃd （ｍｏｄ ｎ）により復
号化するのに対し、ラビン型暗号は、公開鍵ｎと秘密鍵
ｐ，ｑとを用いて、ｐおよびｑを法とする二次方程式ｘ
2 ≡Ｃを解くことにより復号化する。
【０３３６】ここで、注意する事はＲＳＡ型暗号とラビ
ン型暗号の復号化関数は全く異なる点である。ＲＳＡ型
暗号の復号に利用する関数によりラビン型暗号は復号化
できない、この逆も同様である。
【０３３７】
【発明の効果】以上説明したように、本発明によれば、
暗号化にｎ進表現を用いることにより、複数の平文ブロ
ックを一括して暗号化し、この復号化において、ｎ進表
現された最下位桁は、従来の暗号と同等の復号化関数に
よって復号化されるが、最下位桁を除く上位桁は、復号
化された最下位桁の値を利用して、従来の復号化関数よ
り計算時間が十分短い合同式を解くことによって、復号
化することができる。
【０３３８】これにより、従来のＲＳＡ暗号やラビン暗
号と比較して、同程度の強度を持ちながら、復号化速度
を大幅に向上させた暗号通信方法および同方法を実現す
る装置を提供することができる。
【０３３９】例えば、ブロック数をｋとして、ＲＳＡ型
の公開鍵暗号に本発明のｎ進表現暗号を適用するとすれ
ば、従来のＲＳＡ型の暗号化処理では、各ブロック毎に
ｎを法とするｅ乗演算を行うのに対して、本発明のｎ進
表現暗号では、ｋブロックをひとまとめにしてｎを法と
するｅ乗演算を行うが、ビット数がｋ倍になっているの
で、暗号化処理の速度は、従来とほぼ同等である。
【０３４０】一方、従来のＲＳＡ型の復号化処理では、
各ブロック毎にｎを法とするｄ乗演算を行うのに対し
て、本発明のｎ進表現暗号では、最初のブロックのみｎ
を法とするｄ乗演算を行い、これに続くブロックでは、
ｄ乗演算より遥かに処理時間が短い合同式処理を行うこ
とにより復号化する。
【０３４１】これにより、ｄ乗演算処理に対する合同式
処理の処理時間比をｐと仮定すると、ｋブロック全てを
復号化する処理時間について、従来技術と本発明との比
は、ｋ：｛１＋（ｋ−１）ｐ｝となる。例えば、ｐ＝
０．５，ｋ＝１０とすると、本発明を適用した暗号化方
式における復号化処理時間は、従来より４５％短縮さ
れ、迅速な復号化を行えるという効果を奏する。
【０３４２】また、本発明によれば、認証装置としても
利用可能であり、ひとつの装置で暗号化通信と認証の両
用が可能となるような暗号化通信方法および認証方法お
よびこれらを実現する装置を提供することができる。
【０３４３】なお、本発明に係るｎ進表現暗号のブロッ
ク数ｋを１とすると、従来のＲＳＡ暗号またはラビン暗
号等の公開鍵型暗号となる。
【０３４４】また、一ブロック目を公開鍵Ｎのビット長
程度の乱数とした場合、一ブロック目が解読の情報を与
えることがなくなるため、ＲＳＡ暗号やラビン暗号に対
して知られている同じ平文を複数の通信相手に送る場合
（同報通信）、２個の平文に多項式関係がある場合、平
文のビット数が小さい場合など、簡単に解読可能である
という欠点を克服できる。
【０３４５】また、本発明によれば、復号化処理に関数
テーブルの参照の技法を用いることなく、より簡潔な同
じループの計算を繰りかえすことにより復号化処理装置
を構成することができるので、復号化の為に必要なメモ
リ容量を節約するとともに、復号化処理を大幅に高速化
することができる。
【図面の簡単な説明】
【図１】本発明に係るＮ進表現暗号をＲＳＡ型公開鍵暗
号に適用した暗号化通信装置の全体構成を示すブロック
図である。
【図２】本発明に係るＮ進表現暗号をＲＳＡ型公開鍵暗
号に適用した認証装置の全体構成を示すブロック図であ
る。
【図３】図１の暗号化通信装置の一部を構成する復号化
装置の詳細ブロック図である。
【図４】図２の認証装置の一部を構成する認証文生成装
置の詳細ブロック図である。
【図５】本発明に係るＮ進表現暗号をラビン型公開鍵暗
号に適用した暗号化通信装置の全体構成を示すブロック
図である。
【図６】本発明に係るＮ進表現暗号をラビン型公開鍵暗
号に適用した認証装置の全体構成を示すブロック図であ
る。
【図７】鍵生成処理部の処理内容の概略を示すフローチ
ャートである。
【図８】平文分割処理部の処理内容の概略を示すフロー
チャートである。
【図９】鍵生成処理部の処理内容の詳細を示すフローチ
ャートである。
【図１０】図１の暗号化通信装置の一部を構成する暗号
化装置の動作を説明するフローチャートである。
【図１１】図１の暗号化通信装置の一部を構成する復号
化装置の動作を説明するフローチャートである。
【図１２】図２の認証装置の一部を構成する認証文生成
装置の動作を説明するフローチャートである。
【図１３】図２の認証装置の一部を構成する認証文生成
装置の動作を説明するフローチャートである。
【図１４】図２の認証装置の一部を構成する認証文検証
装置の動作を説明するフローチャートである。
【図１５】図５の暗号化通信装置の一部を構成する暗号
化装置の動作を説明するフローチャートである。
【図１６】図５の暗号化通信装置の一部を構成する復号
化装置の動作を説明するフローチャートである。
【図１７】図５の暗号化通信装置の一部を構成する復号
化装置の動作のうち、上位桁の復号化動作を説明するフ
ローチャートである。
【図１８】図６の認証装置の一部を構成する認証文生成
装置の動作を説明するフローチャートである。
【図１９】図６の認証装置の一部を構成する認証文生成
装置の動作のうち、上位桁の暗号化動作を説明するフロ
ーチャートである。
【図２０】図６の認証装置の一部を構成する認証文検証
装置の動作を説明するフローチャートである。
【図２１】本発明に係るＮ進表現暗号をＲＳＡ型公開鍵
暗号に適用した暗号化通信装置の変形例の構成を示すブ
ロック図である。
【図２２】本発明に係るＮ進表現暗号をラビン型公開鍵
暗号に適用した暗号化通信装置の変形例の構成を示すブ
ロック図である。
【図２３】ＲＳＡ型Ｎ進表現暗号の上位桁復号化方法を
説明するフローチャートである。
【図２４】ＲＳＡ型Ｎ進表現暗号の上位桁認証文暗号化
方法を説明するフローチャートである。
【図２５】ラビン型Ｎ進表現暗号の復号化方法を説明す
るフローチャートである。
【図２６】ラビン型Ｎ進表現暗号の上位桁認証文暗号化
方法を説明するフローチャートである。
【符号の説明】
１１…暗号化通信装置、２１…鍵生成処理部、３１…暗
号化装置、３３…平文分割処理部、３５…データ結合
部、３７…暗号化処理部、４１…復号化装置、４３…最
下位桁復号化処理部、４５…上位桁復号化処理部、４７
…データ連結部、５１…通信路。
───────────────────────────────────────────────────── フロントページの続き (51)Int.Cl.6 識別記号 ＦＩ Ｈ０４Ｌ 9/00 ６７５Ｂ

Claims (48)

    【特許請求の範囲】
  1. 【請求項１】暗号化の対象である平文データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる第１の秘密鍵データと、 ｄを値とする第２の秘密鍵データと、 ｐとｑとの積Ｎを値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いる公開鍵型のＮ進表現暗号による通信方法であっ
    て、 前記Ｎを基数とするＮ進位取り記数法により前記平文デ
    ータをｋ桁のＮ進数データとして表現する第１の過程
    と、 前記ｋ桁のＮ進数データに対して、第１及び第２の公開
    鍵データを使用する演算により、前記平文データを暗号
    化した暗号文データを得る第２の過程と、 第１の公開鍵データ及び第２の秘密鍵データを用いて、
    前記暗号文データから前記Ｎ進数の最下位桁の値を復号
    化する第３の過程と、 前記復号化された最下位桁の値を用いて、前記Ｎ進数の
    上位の桁の値を順次復号化する第４の過程と、 前記復号化されたＮ進数の各桁の値を用いて前記平文デ
    ータを復元する第５の過程と、 を備えたことを特徴とするＮ進表現暗号による通信方
    法。
  2. 【請求項２】前記第１の過程は、前記平文データの先頭
    に予め第１の公開鍵データＮのビット長程度の乱数を連
    接して連接データを作成し、以下この連接データを平文
    データとして、前記Ｎを基数とするＮ進位取り記数法に
    よりｋ桁のＮ進数データとして表現する過程であること
    を特徴とする請求項１に記載のＮ進表現暗号による通信
    方法。
  3. 【請求項３】暗号化の対象である平文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成する公開鍵型のＮ進表現暗号による暗号化方法であっ
    て、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データを複数のブロックに分割するとともに、分割さ
    れたブロックの数ｋを計数する第１の過程と、 前記分割された各ブロックのデータを、それぞれＮ進数
    の形態で表現する第２の過程と、 前記平文データの全体が、ｋ桁のＮ進数として位取りさ
    れるように各ブロックのデータを順次結合する第３の過
    程と、 Ｎのｋ乗を法として、前記結合されたデータをｅ乗した
    値である暗号文データを計算する第４の過程と、 を備えたことを特徴とするＮ進表現暗号による暗号化方
    法。
  4. 【請求項４】暗号化の対象である平文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成する公開鍵型のＮ進表現暗号による暗号化プログラム
    を格納した記憶媒体であって、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データを複数のブロックに分割するとともに、分割さ
    れたブロックの数ｋを計数し、 前記分割された各ブロックのデータを、それぞれＮ進数
    の形態で表現し、 前記平文データの全体が、ｋ桁のＮ進数として位取りさ
    れるように各ブロックのデータを順次結合し、 Ｎのｋ乗を法として、前記結合されたデータをｅ乗した
    値である暗号文データを計算すること、 を特徴とするＮ進表現暗号による暗号化プログラムを格
    納した記憶媒体。
  5. 【請求項５】暗号化の対象である平文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成する公開鍵型のＮ進表現暗号による暗号化装置であっ
    て、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データを複数のブロックに分割するとともに、分割さ
    れたブロックの数ｋを計数する平文分割手段と、 前記平文分割手段が分割した各ブロックのデータを順次
    格納する記憶手段と、 前記記憶された各ブロックのデータが１つのＮ進数の各
    桁の値を示すように、各ブロックのデータを順次結合し
    た結合データを生成するデータ結合手段と、 Ｎのｋ乗を法として、前記結合データをｅ乗した値であ
    る暗号文データを生成する暗号化手段と、 を備えたことを特徴とするＮ進表現暗号による暗号化装
    置。
  6. 【請求項６】平文データからＮ進表現暗号により暗号化
    された暗号文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、前記暗号文データに該当する平文データを復
    元する公開鍵型のＮ進表現暗号の復号化方法であって、 Ｎを法として前記暗号文データの値をｄ乗することによ
    って、前記平文データをＮ進位取り記数法で表現したと
    きの最下位桁の値Ｍ0 を求める第１の過程と、 このＭ0 に基づいて、１次合同式を用いて、自然数の中
    から、その値をｅ乗した値に対して、Ｎのｋ乗を法とす
    る剰余が前記暗号文データの値に等しくなるような自然
    数を、Ｍ0 を最下位桁とし桁数がｋであるＮ進数表現の
    形で求める第２の過程（以下、この過程を上位桁復号化
    過程と称する）と、 これらのＮ進数の各桁の数値を順次連結することによっ
    て平文データを生成する第３の過程と、 を備えたことを特徴とするＮ進表現暗号の復号化方法。
  7. 【請求項７】前記上位桁復号化過程は、 前記Ｍ0 を最下位桁の値とし桁数がｋであるＮ進数とし
    て複数の平文ブロックを表現したもの全体をｅ乗した形
    である暗号文を、前記ｅ乗を展開して得られるＮに関す
    るｋ−１次の多項式に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、低次の係数から高次の係数へ昇順
    に順次求める係数値計算過程と、 これらの係数値を使って、Ｎを法とする１次合同式を解
    くことにより、前記Ｎ進数における上位の桁の値を順次
    確定していく上位桁計算過程と、 を備えたことを特徴とする請求項６に記載のＮ進表現暗
    号の復号化方法。
  8. 【請求項８】前記係数値計算過程は、 求められた係数の値を係数テーブルに順次記憶するとと
    もに、該係数テーブルに記憶された低次の係数の値を参
    照することを含むことを特徴とする請求項７に記載のＮ
    進表現暗号の復号化方法。
  9. 【請求項９】前記ｋ桁のＮ進数の各桁の値をＭi （０≦
    ｉ≦ｋ−１）とするとき、 前記上位桁復号化過程は、 前記最下位桁の値Ｍ0 と、第１の公開鍵データＮと、第
    ２の公開鍵データｅと、暗号文データＣと、ブロック数
    データｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基
    づいてＭi を求める同一の写像もしくは同一の計算式に
    より、再帰的にＭ1 からＭk-1 までを順次復号化するこ
    とを特徴とする請求項６に記載のＮ進表現暗号の復号化
    方法。
  10. 【請求項１０】平文データからＮ進表現暗号により暗号
    化された暗号文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、前記暗号文データに該当する平文データを復
    元する公開鍵型のＮ進表現暗号の復号化プログラムを格
    納した記憶媒体であって、 Ｎを法として前記暗号文データの値をｄ乗することによ
    って、前記平文データをＮ進位取り記数法で表現したと
    きの最下位桁の値Ｍ0 を求め、 このＭ0 に基づいて、１次合同式を用いて、自然数の中
    から、その値をｅ乗した値に対して、Ｎのｋ乗を法とす
    る剰余が前記暗号文データの値に等しくなるような自然
    数を、Ｍ0 を最下位桁とし桁数がｋであるＮ進数表現の
    形で求め、 これらのＮ進数の各桁の数値を順次連結することによっ
    て平文データを生成する、 ことを特徴とするＮ進表現暗号の復号化プログラムを格
    納した記憶媒体。
  11. 【請求項１１】平文データからＮ進表現暗号により暗号
    化された暗号文データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、前記暗号文データに該当する平文データを復
    元するＮ進表現暗号の復号化装置であって、 Ｎを法として、前記暗号文データをｄ乗した値の剰余を
    求めることにより、前記平文データをＮ進位取り記数法
    で表現したときの最下位桁の値Ｍ0 を得る最下位桁復号
    化手段と、 このＭ0 に基づいて、自然数の中から、Ｎのｋ乗を法と
    して、その値をｅ乗した値が前記暗号文データの値に等
    しくなるような自然数を、Ｍ0 を最下位桁とし桁数がｋ
    であるＮ進数表現の形で求める上位桁復号化手段と、 前記Ｎ進数の各桁の数値を順次連結することによって平
    文データを生成するデータ連結手段と、を備えてなり、 前記上位桁復号化手段は、 前記Ｍ0 を最下位桁の値とし桁数がｋであるＮ進数とし
    て複数の平文ブロックを表現したもの全体をｅ乗した形
    である暗号文を、前記ｅ乗を展開して得られるＮに関す
    るｋ−１次の多項式に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、低次の係数から高次の係数へ昇順
    に順次求める係数値計算手段と、 この係数計算手段により求められた係数値を使って、Ｎ
    を法とする１次合同式を解くことにより、前記Ｎ進数に
    おける上位の桁の値を順次確定していく上位桁計算手段
    と、 を備えたことを特徴とするＮ進表現暗号の復号化装置。
  12. 【請求項１２】前記係数計算手段は、 既に求められた低次の係数の値を順次記憶した係数テー
    ブル記憶手段と、 この係数テーブル記憶手段から求めるべき係数より低次
    の係数値を読み出す読出し手段と、 を備えたことを特徴とする請求項１１に記載のＮ進表現
    暗号の復号化装置。
  13. 【請求項１３】平文データＭからＮ進表現暗号により暗
    号化された暗号文データＣと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、前記暗号文データＣに該当する平文データＭ
    を復元するＮ進表現暗号の復号化装置であって、 Ｎを法として、前記暗号文データをｄ乗した値の剰余を
    求めることにより、前記平文データをＮ進位取り記数法
    で表現したときの最下位桁の値Ｍ0 を得る最下位桁復号
    化手段と、 前記最下位桁の値Ｍ0 と、第１の公開鍵データＮと、第
    ２の公開鍵データｅと、暗号文データＣと、ブロック数
    データｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基
    づいてＭi （１≦ｉ≦ｋ−１）を求める同一の写像もし
    くは同一の計算式により、再帰的に前記Ｎ進数表現の上
    位桁であるＭ1 からＭk-1 までを順次復号化する上位桁
    復号化手段と、 前記Ｎ進数の各桁の数値を順次連結することによって平
    文データを生成するデータ連結手段と、 を備えたことを特徴とするＮ進表現暗号の復号化装置。
  14. 【請求項１４】認証対象である認証文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる第１の秘密鍵データと、 ｄを値とする第２の秘密鍵データと、 ｐとｑとの積Ｎを値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いる公開鍵型のＮ進表現暗号による認証方法であっ
    て、 前記認証文データに基づいて認証子データｈ(Ｍ)を生成
    する第１の過程と、 第１の公開鍵データ及び第２の秘密鍵データを用いる演
    算により、前記認証子データｈ(Ｍ)からＮ進数表現され
    た暗号化認証子データｈ(Ｃ)の最下位桁の値ｈ(Ｃ)0 を
    生成する第２の過程と、 前記生成された最下位桁の値ｈ(Ｃ)0 を用いて、前記Ｎ
    進数表現された暗号化認証子データの上位の桁の値を順
    次生成する第３の過程と、 前記生成されたＮ進数の各桁の値を示すブロックを順次
    連結して暗号化認証子データｈ(Ｃ)を生成する第４の過
    程と、 前記暗号化認証子データｈ(Ｃ)と前記Ｎ進数の桁数ｋと
    認証文データＭとを認証相手に送信する第５の過程と、 前記暗号化認証子データ全体を１つのｋ桁のＮ進数とし
    て、これに対して、第１及び第２の公開鍵データを使用
    する演算により、前記暗号化認証子データｈ(Ｃ)から復
    号化された認証子データｈ(Ｍ)を得る第６の過程と、 前記復号化された認証子データｈ(Ｍ)と前記認証文デー
    タＭとを用いて認証を行う第７の過程と、 を備えたこと特徴とするＮ進表現暗号による認証方法。
  15. 【請求項１５】認証対象となる認証子データｈ(Ｍ)と、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成方法
    であって、 Ｎを法として前記認証子データの値をｄ乗した値を計算
    し、この値を前記認証子データｈ(Ｍ)を暗号化してＮ進
    表現したときの最下位桁の値ｈ(Ｃ)0 とする第１の過程
    と、 このｈ(Ｃ)0 に基づいて、自然数の中から、Ｎのｋ乗を
    法としてその値をｄ乗した値が前記認証子データｈ(Ｍ)
    の値に等しくなるような自然数を、ｈ(Ｃ)0 を最下位桁
    の値としたｋ桁のＮ進数として表現した形で求める第２
    の過程（以下、この過程を認証子上位桁暗号化過程と称
    する）と、 このＮ進数の各桁を表わす数値データを順次連結するこ
    とによって、暗号化認証子データｈ(Ｃ)を生成する第３
    の過程と、 を備えたことを特徴とするＮ進表現暗号による認証文生
    成方法。
  16. 【請求項１６】前記認証子上位桁暗号化過程は、 前記ｈ(Ｃ)0 を最下位桁の値とし桁数がｋであるＮ進数
    として前記認証子データｈ(Ｍ)を表現したもの全体をｄ
    乗した形である暗号化認証子データｈ(Ｃ)を、前記ｄ乗
    を展開して得られるＮに関するｋ−１次の多項式に対応
    させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記認証子
    データを変数とする多項式関数とみなして、前記認証子
    データｈ(Ｍ)及び前記Ｎ進数の既に求められた下位の桁
    の値に基づいて、低次の係数から高次の係数へ昇順に順
    次求める係数値計算過程と、 これらの係数値を使って、Ｎを法とする１次合同式を解
    くことにより、前記Ｎ進数における上位の桁の値を順次
    確定していく上位桁計算過程と、 を備えたことを特徴とする請求項１５に記載のＮ進表現
    暗号による認証文生成方法。
  17. 【請求項１７】前記係数値計算過程は、 求められた係数の値を係数テーブルに順次記憶するとと
    もに、該係数テーブルに記憶された低次の係数の値を参
    照することを含むことを特徴とする請求項１６に記載の
    Ｎ進表現暗号による認証文生成方法。
  18. 【請求項１８】前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i
    （０≦ｉ≦ｋ−１）とするとき、 前記認証子上位桁暗号化過程は、 前記最下位桁の値ｈ(Ｃ)0 と、第１の公開鍵データＮ
    と、第２の公開鍵データｅと、認証子データｈ(Ｍ)と、
    ブロック数データｋとを入力として、ｈ(Ｃ)0 ，ｈ(Ｃ)
    1 ，…，ｈ(Ｃ)i-1 に基づいてｈ(Ｃ)i を求める同一の
    写像もしくは同一の計算式により、再帰的にｈ(Ｃ)1 か
    らｈ(Ｃ)k-1 までを順次暗号化することを特徴とする請
    求項１５に記載のＮ進表現暗号による認証文生成方法。
  19. 【請求項１９】認証対象となる認証子データｈ(Ｍ)と、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成プロ
    グラムを格納した記憶媒体であって、 Ｎを法として前記認証子データの値をｄ乗した値を計算
    し、この値を前記認証子データｈ(Ｍ)を暗号化してＮ進
    表現したときの最下位桁の値ｈ(Ｃ)0 とし、 このｈ(Ｃ)0 に基づいて、自然数の中から、Ｎのｋ乗を
    法としてその値をｄ乗した値が前記認証子データｈ(Ｍ)
    の値に等しくなるような自然数を、ｈ(Ｃ)0 を最下位桁
    の値としたｋ桁のＮ進数として表現した形で求め、 このＮ進数の各桁を表わす数値データを順次連結するこ
    とによって、暗号化認証子データｈ(Ｃ)を生成する、 ことを特徴とするＮ進表現暗号による認証文生成プログ
    ラムを格納した記憶媒体。
  20. 【請求項２０】認証対象となる認証子データｈ(Ｍ)と、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成装置
    であって、 Ｎを法として、前記認証子データの値をｄ乗した値ｈ
    (Ｃ)0 を計算する最下位桁計算手段と、 ｈ(Ｃ)0 に基づいて、自然数の中から、Ｎのｋ乗を法と
    してその値をｄ乗した値が、前記認証子データの値に等
    しくなるような自然数を、ｈ(Ｃ)0 を最下位桁の値とし
    たｋ桁のＮ進数として表現した形で求める認証子上位桁
    暗号化手段と、 このＮ進数の各桁を表わす数値データを順次連結するこ
    とによって、暗号化認証子データｈ(Ｃ)を生成する連結
    手段と、 を備えてなり、 前記認証子上位桁暗号化手段は、 前記ｈ(Ｃ)0 を最下位桁の値とし桁数がｋであるＮ進数
    として前記認証子データｈ（Ｍ）を表現したもの全体を
    ｄ乗した形である暗号化認証子データｈ（Ｃ）を、前記
    ｄ乗を展開して得られるＮに関するｋ−１次の多項式に
    対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記認証子
    データを変数とする多項式関数とみなして、前記認証子
    データｈ(Ｍ)及び前記Ｎ進数の既に求められた下位の桁
    の値に基づいて、低次の係数から高次の係数へ昇順に順
    次求める係数計算手段と、 これらの係数値を使って、Ｎを法とする１次合同式を解
    くことにより、前記Ｎ進数におけるより上位の桁の値を
    順次確定していく上位桁計算手段と、 を備えたことを特徴とするＮ進表現暗号による認証文生
    成装置。
  21. 【請求項２１】前記係数計算手段は、 既に求められた低次の係数の値を順次記憶した係数テー
    ブル記憶手段と、 この係数テーブル記憶手段から求めるべき係数より低次
    の係数値を読み出す読出し手段と、 を備えたことを特徴とする請求項２０に記載のＮ進表現
    暗号による認証文生成装置。
  22. 【請求項２２】認証対象となる認証子データｈ(Ｍ)と、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 ｄを値とする第２の秘密鍵データと、 ２以上の整数であるｋを値とするブロック数データと、
    を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成装置
    であって、 Ｎを法として、前記認証子データの値をｄ乗した値ｈ
    (Ｃ)0 を計算する最下位桁計算手段と、 ｈ(Ｃ)0 に基づいて、自然数の中から、Ｎのｋ乗を法と
    してその値をｄ乗した値が、前記認証子データの値に等
    しくなるような自然数を、ｈ(Ｃ)0 を最下位桁の値とし
    たｋ桁のＮ進数として表現した形で求める認証子上位桁
    暗号化手段と、 このＮ進数の各桁を表わす数値データを順次連結するこ
    とによって、暗号化認証子データｈ(Ｃ)を生成する連結
    手段と、を備えてなり、 前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i （０≦ｉ≦ｋ−
    １）とするとき、 前記認証子上位桁暗号化手段は、前記最下位桁の値ｈ
    (Ｃ)0 と、第１の公開鍵データＮと、第２の公開鍵デー
    タｅと、認証子データｈ(Ｍ)と、ブロック数データｋと
    を入力として、ｈ(Ｃ)0 ，ｈ(Ｃ)1 ，…，ｈ(Ｃ)i-1 に
    基づいてｈ(Ｃ)iを求める同一の写像もしくは同一の計
    算式により、再帰的にｈ(Ｃ)1 からｈ(Ｃ)k-1 までを順
    次暗号化することを特徴とするＮ進表現暗号による認証
    文生成装置。
  23. 【請求項２３】認証対象である認証文データＭと、 この認証文データから前記請求項１５、１６、１７、１
    ８、２０、２１、２２のいずれか一項に記載の方法また
    は装置により生成された暗号化認証子データｈ(Ｃ)と、 この暗号化認証子データｈ(Ｃ)のブロック数ｋを値とす
    るブロック数データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 を用いて、前記認証文データＭ及びまたは前記暗号化認
    証子データｈ(Ｃ)が正当であるか否かを判別する認証文
    検証方法であって、 前記暗号化認証子データｈ(Ｃ)の各ブロックをｋ桁のＮ
    進数の各桁として順次結合する第１の過程と、 Ｎのｋ乗を法として、この結合されたデータをｅ乗した
    値である復号化された認証子データｈ(Ｍ)を求める第２
    の過程と、 この復号化された認証子データｈ(Ｍ)と前記認証文デー
    タＭに基づいて生成された認証子データｈ(Ｍ)′とを比
    較し、この両者が一致していた場合は、一連の認証ない
    し検証過程が正常であったと判定し、 この両者が不一致であった場合は、一連の認証ないし検
    証過程のいずれかに異常があったと判定する第３の過程
    と、 を備えたことを特徴とするＮ進表現暗号による認証文検
    証方法。
  24. 【請求項２４】認証対象である認証文データＭと、 この認証文データから前記請求項１５、１６、１７、１
    ８、２０、２１、２２のいずれか一項に記載の方法また
    は装置により生成された暗号化認証子データｈ(Ｃ)と、 この暗号化認証子データｈ(Ｃ)のブロック数ｋを値とす
    るブロック数データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 を用いて、前記認証文データＭ及びまたは前記暗号化認
    証子データｈ(Ｃ)が正当であるか否かを判別する認証文
    検証プログラムを格納した記憶媒体であって、 前記暗号化認証子データｈ(Ｃ)の各ブロックをｋ桁のＮ
    進数の各桁として順次結合し、 Ｎのｋ乗を法として、この結合されたデータをｅ乗した
    値である復号化された認証子データｈ(Ｍ)を求め、 この復号化された認証子データｈ(Ｍ)と前記認証文デー
    タＭに基づいて生成された認証子データｈ(Ｍ)′とを比
    較し、この両者が一致していた場合は、一連の認証ない
    し検証過程が正常であったと判定し、 この両者が不一致であった場合は、一連の認証ないし検
    証過程のいずれかに異常があったと判定する、 ことを特徴とするＮ進表現暗号による認証文検証プログ
    ラムを格納した記憶媒体。
  25. 【請求項２５】認証対象である認証文データＭと、 この認証文データＭから前記請求項１５、１６、１７、
    １８、２０、２１、２２のいずれか一項に記載の方法ま
    たは装置により生成された暗号化認証子データｈ(Ｃ)
    と、 この暗号化認証子データｈ(Ｃ)のブロック数ｋを値とす
    るブロック数データと、 それぞれｐとｑとを値とする２つの素数データの積Ｎを
    値とする第１の公開鍵データと、 ｅを値とする第２の公開鍵データと、 を用いて、前記認証文データＭ及びまたは前記暗号化認
    証子データｈ(Ｃ)が正当であるか否かを判別する認証文
    検証装置であって、 前記認証文データＭをハッシュ化し、ハッシュ化認証子
    データｈ(Ｍ)′を生成するハッシュ化手段と、 前記暗号化認証子データｈ(Ｃ)の各ブロックをｋ桁のＮ
    進数の各桁として順次結合する結合手段と、 Ｎのｋ乗を法として、この結合されたデータをｅ乗した
    値を求めて復号化された復号化認証子データｈ(Ｍ)を得
    る認証子復号化手段と、 前記復号化認証子データｈ(Ｍ)と前記ハッシュ化認証子
    データｈ(Ｍ)′とを比較し、この両者が一致していた場
    合は、一連の認証ないし検証過程が正常であったと判定
    し、この両者が不一致であった場合は、一連の認証ない
    し検証過程のいずれかに異常があったと判定する照合判
    定手段と、 を備えたことを特徴とするＮ進表現暗号による認証文検
    証装置。
  26. 【請求項２６】暗号化の対象である平文データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いた公開鍵型のＮ進表現暗号による通信および認証
    方法であって、 前記平文データを、Ｎの剰余類の範囲でｋ個のブロック
    に分割する第１の過程と、 前記分割された各ブロックの値をＮ進数の各桁の値とす
    るとともに、Ｎを基数とするＮ進位取り記数法により前
    記平文データをｋ桁のＮ進数として表現する第２の過程
    と、 前記ブロック数ｋを第２の公開鍵データとし、前記ｋ桁
    のＮ進数に対して、公開鍵データを用いる演算により、
    前記平文データに該当する暗号文データを得る第３の過
    程と、 前記秘密鍵データと、前記公開鍵データとを用いて、前
    記暗号文データから前記ｋ桁のＮ進数の最下位桁の値を
    復号化する第４の過程と、 前記復号化された最下位桁の値を用いて、前記ｋ桁のＮ
    進数の上位の桁の値を順次復号化する第５の過程と、 を備えたことを特徴とするＮ進表現暗号による通信方
    法。
  27. 【請求項２７】前記第１の過程は、前記平文データの先
    頭に予め第１の公開鍵データＮのビット長程度の乱数を
    連接して連接データを作成し、以下この連接データを平
    文データとして、前記Ｎを基数とするＮ進位取り記数法
    によりｋ桁のＮ進数データとして表現する過程であるこ
    とを特徴とする請求項２６に記載のＮ進表現暗号による
    通信方法。
  28. 【請求項２８】暗号化の対象である平文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れた秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成する公開鍵型のＮ進表現暗号による暗号化方法であっ
    て、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データＭをｋ個のブロックに分割する第１の過程と、 前記平文データＭ全体がｋ桁のＮ進数として位取りされ
    るように各ブロックのデータを順次結合する第２の過程
    と、 前記結合されたデータを２乗する第３の過程と、 この２乗されたデータに対して、Ｎをｋ乗した数値を法
    とした剰余である暗号文データＣを生成する第４の過程
    と、 を備えたことを特徴とするＮ進表現暗号による暗号化方
    法。
  29. 【請求項２９】暗号化の対象である平文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れた秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成する公開鍵型のＮ進表現暗号による暗号化プログラム
    を格納した記憶媒体であって、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データＭをｋ個のブロックに分割し、 前記平文データＭ全体がｋ桁のＮ進数として位取りされ
    るように各ブロックのデータを順次結合し、 前記結合されたデータを２乗し、 この２乗されたデータに対して、Ｎをｋ乗した数値を法
    とした剰余である暗号文データＣを生成する、 ことを特徴とするＮ進表現暗号による暗号化プログラム
    を格納した記憶媒体。
  30. 【請求項３０】暗号化の対象である平文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 ２以上の整数であるｋを値とするブロック数データと、 を用いて、前記平文データに該当する暗号文データを生
    成するＮ進表現暗号による暗号化装置であって、 各ブロックがＮの剰余類の範囲に収まるように、前記平
    文データＭをｋ個のブロックに分割する平文分割手段
    と、 前記平文データＭ全体がｋ桁のＮ進数として位取りされ
    るように、前記各ブロックのデータを順次結合した結合
    データを生成するデータ結合手段と、 Ｎをｋ乗した数値を法として、前記結合データを２乗す
    ることにより暗号文データＣを生成する暗号化手段と、 を備えたことを特徴とするＮ進表現暗号による暗号化装
    置。
  31. 【請求項３１】暗号化された暗号文データＣと、 ２以上の整数であるｋを値とするブロック数データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 を用いて、前記暗号文データＣに該当する平文データＭ
    を復元する復号化方法であって、 自然数の中から、その値を２乗した値が、Ｎを法として
    暗号文データＣに等しくなるような自然数ｘを、数値ｐ
    を法とする剰余ならびに数値ｑを法とする剰余を用いて
    求め、この値ｘを桁数がｋであるＮ進数の最下位桁の値
    Ｍ0 とする第１の過程と、 Ｍ0 の値と前記暗号文データＣとを含む１次合同式を用
    いて、桁数がｋであるＮ進数の各桁の値を下位から逐次
    求める第２の過程（以下、この過程を上位桁復号化過程
    と称する）と、 このＮ進数の各桁の数値データを順次連結し、全体とし
    て１つのＮ進数データとすることによって、上記暗号文
    データに該当する平文データＭを復元する第３の過程
    と、 を備えたことを特徴とするＮ進表現暗号による復号化方
    法。
  32. 【請求項３２】前記上位桁復号化過程は、 前記Ｍ0 を最下位桁の値とし桁数がｋであるＮ進数とし
    て表現したデータ全体を２乗した形である暗号文を、前
    記２乗を展開して得られるＮに関するｋ−１次の多項式
    に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、このｋ−１次の式の係数値を昇順
    に順次求める過程と、 求めた係数値を使って、Ｎを法とする１次合同式を解く
    ことにより、前記Ｎ進数におけるより上位の桁の値を順
    次確定していく過程と、を含むことを特徴とする請求項
    ３１に記載のＮ進表現暗号の復号化方法。
  33. 【請求項３３】前記ｋ桁のＮ進数の各桁の値をＭi （０
    ≦ｉ≦ｋ−１）とするとき、 前記上位桁復号化過程は、 前記最下位桁の値Ｍ0 と、公開鍵データＮと、暗号文デ
    ータＣと、ブロック数データｋとを入力として、Ｍ0 ，
    Ｍ1 ，…，Ｍi-1 に基づいてＭi を求める同一の写像も
    しくは同一の計算式により、再帰的にＭ1 からＭk-1 ま
    でを順次復号化することを特徴とする請求項３１に記載
    のＮ進表現暗号の復号化方法。
  34. 【請求項３４】暗号化された暗号文データＣと、 ２以上の整数であるｋを値とするブロック数データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 を用いて、前記暗号文データＣに該当する平文データＭ
    を復元する復号化プログラムを格納した記憶媒体であっ
    て、 自然数の中から、その値を２乗した値が、Ｎを法として
    暗号文データＣに等しくなるような自然数ｘを、数値ｐ
    を法とする剰余ならびに数値ｑを法とする剰余を用いて
    求め、この値ｘを桁数がｋであるＮ進数の最下位桁の値
    Ｍ0 とし、 Ｍ0 の値と前記暗号文データＣとを含む１次合同式を用
    いて、桁数がｋであるＮ進数の各桁の値を下位から逐次
    求め、 このＮ進数の各桁の数値データを順次連結し、全体とし
    て１つのＮ進数データとすることによって、上記暗号文
    データに該当する平文データＭを復元する、 ことを特徴とするＮ進表現暗号による復号化プログラム
    を格納した記憶媒体。
  35. 【請求項３５】暗号化された暗号文データＣと、 ２以上の整数であるｋを値とするブロック数データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 を用いて、前記暗号文データＣに該当する平文データＭ
    を復元する復号化装置であって、 自然数の中から、その値を２乗した値が、Ｎを法として
    暗号文データＣに等しくなるような自然数ｘを、数値ｐ
    を法とする剰余ならびに数値ｑを法とする剰余を用いて
    求め、この値ｘを桁数がｋであるＮ進数の最下位桁の値
    Ｍ0 とする最下位桁復号化手段と、 Ｍ0 の値と前記暗号文データＣとを含む１次合同式を解
    くことにより、桁数がｋであるＮ進数の各桁の値を下位
    から逐次求める上位桁復号化手段と、 このＮ進数の各桁の数値データを順次連結し、平文デー
    タＭを復元するデータ連結手段と、 を備えたことを特徴とするＮ進表現暗号の復号化装置。
  36. 【請求項３６】前記上位桁復号化手段は、 前記Ｍ0 を最下位桁の値とし桁数がｋであるＮ進数とし
    て表現したデータ全体を２乗した形である暗号文を、前
    記２乗を展開して得られるＮに関するｋ−１次の多項式
    に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、このｋ−１次の式の係数値を昇順
    に順次求め、この求めた係数値を使って、Ｎを法とする
    １次合同式を解くことにより、前記Ｎ進数におけるより
    上位の桁の値を順次確定していくことを特徴とする請求
    項３５に記載のＮ進表現暗号の復号化装置。
  37. 【請求項３７】前記ｋ桁のＮ進数の各桁の値をＭi （０
    ≦ｉ≦ｋ−１）とするとき、 前記上位桁復号化手段は、前記最下位桁の値Ｍ0 と、公
    開鍵データＮと、暗号文データＣと、ブロック数データ
    ｋとを入力として、Ｍ0 ，Ｍ1 ，…，Ｍi-1 に基づいて
    Ｍi を求める同一の写像もしくは同一の計算式により、
    再帰的にＭ1 からＭk-1 までを順次復号化することを特
    徴とする請求項３５に記載のＮ進表現暗号の復号化装
    置。
  38. 【請求項３８】認証対象である認証文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 ２以上の整数であるｋを値とするブロック数データと、 を用いたＮ進表現暗号による認証方法であって、 前記認証文データＭに基づいて認証子データｈ(Ｍ)を生
    成する第１の過程と、 前記秘密鍵データ及び前記公開鍵データを用いて、前記
    認証子データｈ(Ｍ)をｋ桁のＮ進数に暗号化したときの
    最下位桁の値ｈ(Ｃ)0 を生成する第２の過程と、 前記最下位桁の値を用いて、前記ｋ桁のＮ進数の上位の
    桁の値を順次暗号化する第３の過程と、 前記Ｎ進数の各桁の値を順次連結して、暗号化認証子デ
    ータｈ(Ｃ)を生成する第４の過程と、 前記暗号化認証子データｈ(Ｃ)と認証文データＭとを通
    信する第５の過程と、 前記暗号化認証子データｈ(Ｃ)をｋ個のブロックに分割
    するとともに、この分割された各ブロックの値をＮ進数
    の各桁の値とした結合データを求める第６の過程と、 この結合データ全体を２乗した値からＮのｋ乗を法とす
    る剰余を求めることにより暗号化認証子データｈ(Ｃ)を
    復号化して復号化認証子データｈ(Ｍ)′を得る第７の過
    程と、 この復号化認証子データｈ(Ｍ)′と前記認証文データＭ
    とを用いて認証を行う第８の過程と、 を備えたことを特徴とする公開鍵型のＮ進表現暗号によ
    る認証方法。
  39. 【請求項３９】認証対象となる認証文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成方法
    であって、 前記認証文データＭをハッシュ化して認証子データｈ
    (Ｍ)を生成する第１の過程と、 自然数の中から、その値ｘを２乗した値が、Ｎを法とし
    て前記認証子データｈ(Ｍ)に等しくなるような自然数ｘ
    を、数値ｐを法とする剰余ならびに数値ｑを法とする剰
    余を用いて求め、この自然数の値ｘを桁数がｋであるＮ
    進数の最下位桁の値ｈ(Ｃ)0 とする第２の過程と、 この最下位桁の値ｈ(Ｃ)0 と前記認証子データｈ(Ｍ)を
    含む１次合同式を解くことにより、桁数がｋであるＮ進
    数の各桁の数値を下位から順次求める第３の過程（以
    下、この過程を認証子上位桁暗号化過程と称する）と、 この求められた各桁の数値を順次連結し、全体として１
    つのＮ進数データとすることによって、暗号化認証子デ
    ータｈ(Ｃ)を生成する第４の過程と、 を備えたことを特徴とするＮ進表現暗号による認証文生
    成方法。
  40. 【請求項４０】前記認証子上位桁暗号化過程は、 前記ｈ(Ｃ)0 を最下位桁の値とし桁数がｋであるＮ進数
    として表現したものを全体を２乗した形である暗号文
    を、前記２乗を展開して得られるＮに関するｋ−１次の
    多項式に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、このｋ−１次の式の係数値を昇順
    に順次求め、求めた係数値を使って、Ｎのべき乗を法と
    する１次合同式を解くことにより、前記Ｎ進数における
    上位の桁の値を順次確定していくことによって実現する
    ことを特徴とする請求項３９に記載のＮ進表現暗号によ
    る認証文生成方法。
  41. 【請求項４１】前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i
    （０≦ｉ≦ｋ−１）とするとき、 前記認証子上位桁暗号化過程は、前記最下位桁の値ｈ
    (Ｃ)0 と、公開鍵データＮと、認証子データｈ(Ｍ)と、
    ブロック数データｋとを入力として、ｈ(Ｃ)0 ，ｈ(Ｃ)
    1 ，…，ｈ(Ｃ)i-1 に基づいてｈ(Ｃ)i を求める同一の
    写像もしくは同一の計算式により、再帰的にｈ(Ｃ)1 か
    らｈ(Ｃ)k-1 までを順次暗号化することを特徴とする請
    求項３９に記載のＮ進表現暗号による認証文生成方法。
  42. 【請求項４２】認証対象となる認証文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑとの積Ｎを値とする公開鍵データと、 を用いて、 前記認証子データｈ(Ｍ)を暗号化した暗号化認証子デー
    タｈ(Ｃ)を生成するＮ進表現暗号による認証文生成プロ
    グラムを格納した記憶媒体であって、 前記認証文データＭをハッシュ化して認証子データｈ
    (Ｍ)を生成し、 自然数の中から、その値ｘを２乗した値が、Ｎを法とし
    て前記認証子データｈ(Ｍ)に等しくなるような自然数ｘ
    を、数値ｐを法とする剰余ならびに数値ｑを法とする剰
    余を用いて求め、この自然数の値ｘを桁数がｋであるＮ
    進数の最下位桁の値ｈ(Ｃ)0 とし、 この最下位桁の値ｈ(Ｃ)0 と前記認証子データｈ(Ｍ)を
    含む１次合同式を解くことにより、桁数がｋであるＮ進
    数の各桁の数値を下位から順次求め、 この求められた各桁の数値を順次連結し、全体として１
    つのＮ進数データとすることによって、暗号化認証子デ
    ータｈ(Ｃ)を生成する、 ことを特徴とするＮ進表現暗号による認証文生成プログ
    ラムを記憶した記憶媒体。
  43. 【請求項４３】認証対象となる認証文データＭと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れる秘密鍵データと、 ｐとｑの積Ｎを値とする公開鍵データと、 を用いて、 前記認証文データＭに基づいて生成された認証子データ
    ｈ(Ｍ)を暗号化した暗号化認証子データｈ(Ｃ)を生成す
    るＮ進表現暗号による認証文生成装置であって、 前記認証文データＭをハッシュ化して認証子データｈ
    (Ｍ)を生成するハッシュ化手段と、 自然数の中から、その値ｘを２乗した値が、Ｎを法とし
    て前記認証子データｈ(Ｍ)に等しくなるような自然数ｘ
    を、数値ｐを法とする剰余ならびに数値ｑを法とする剰
    余を用いて求め、この自然数の値ｘを桁数がｋであるＮ
    進数の最下位桁の値ｈ(Ｃ)0 とする最下位桁暗号化手段
    と、 この最下位桁の値ｈ(Ｃ)0 と前記認証子データｈ(Ｍ)を
    含む１次合同式を解くことにより、桁数がｋであるＮ進
    数の各桁の数値を下位から順次求める認証子上位桁暗号
    化手段と、 この求められた各桁の数値を順次連結し、全体として１
    つのＮ進数データとすることによって、暗号化認証子デ
    ータｈ(Ｃ)を生成する連結手段と、 を備えたことを特徴とするＮ進表現暗号による認証文生
    成装置。
  44. 【請求項４４】前記認証子上位桁暗号化手段は、 前記ｈ(Ｃ)0 を最下位桁の値とし桁数がｋであるＮ進数
    として表現したものを全体を２乗した形である暗号文
    を、前記２乗を展開して得られるＮに関するｋ−１次の
    多項式に対応させ、 該ｋ−１次の多項式のそれぞれの係数値を、前記複数の
    平文ブロックを変数とする多項式関数とみなして、 前記暗号文データ及び前記Ｎ進数の既に求められた下位
    の桁の値に基づいて、このｋ−１次の式の係数値を昇順
    に順次求める係数値計算手段と、 この求められた係数値を使って、Ｎのべき乗を法とする
    １次合同式を解くことにより、前記Ｎ進数におけるより
    上位の桁の値を順次確定していく上位桁計算手段と、 を備えることを特徴とする請求項４３に記載のＮ進表現
    暗号による認証文生成装置。
  45. 【請求項４５】前記ｋ桁のＮ進数の各桁の値をｈ(Ｃ)i
    （０≦ｉ≦ｋ−１）とするとき、 前記認証子上位桁暗号化手段は、前記最下位桁の値ｈ
    (Ｃ)0 と、公開鍵データＮと、認証子データｈ(Ｍ)と、
    ブロック数データｋとを入力として、ｈ(Ｃ)0 ，ｈ(Ｃ)
    1 ，…，ｈ(Ｃ)i-1 に基づいてｈ(Ｃ)i を求める同一の
    写像もしくは同一の計算式により、再帰的にｈ(Ｃ)1 か
    らｈ(Ｃ)k-1 までを順次暗号化することを特徴とする請
    求項４３に記載のＮ進表現暗号による認証文生成装置。
  46. 【請求項４６】認証対象となる認証文データＭと、 前記請求項３９、４０、４１、４３、４４、４５のいず
    れか１項に記載の方法または装置で暗号化された暗号化
    認証子ｈ(Ｃ)データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れた秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 を用いて、 前記認証文データＭ及びまたは前記暗号化認証子データ
    ｈ(Ｃ)が正当であるか否かを判別するＮ進表現暗号によ
    る認証文検証方法であって、 暗号化認証子データｈ(Ｃ)を２乗した値に対して、Ｎの
    ｋ乗を法とする剰余である復号化認証子データｈ(Ｍ)を
    求め、 この復号化認証子データｈ(Ｍ)と、前記認証対象となる
    認証文データＭをハッシュ化したハッシュ化認証子デー
    タｈ(Ｍ)′が一致していた場合は、一連の認証ないし検
    証過程が正常であったと判定し、この復号化認証子デー
    タｈ(Ｍ)と、前記認証対象となる認証文データＭをハッ
    シュ化したハッシュ化認証子データｈ(Ｍ)′が不一致で
    あった場合は、一連の認証ないし検証過程のいずれかに
    異常があったと判定する、ことを特徴とするＮ進表現暗
    号による認証文検証方法。
  47. 【請求項４７】認証対象となる認証文データＭと、 前記請求項３９、４０、４１、４３、４４、４５のいず
    れか１項に記載の方法または装置で暗号化された暗号化
    認証子ｈ(Ｃ)データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れた秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 を用いて、 前記認証文データＭ及びまたは前記暗号化認証子データ
    ｈ(Ｃ)が正当であるか否かを判別するＮ進表現暗号によ
    る認証文検証プログラムを格納した記憶媒体であって、 暗号化認証子データｈ(Ｃ)を２乗した値に対して、Ｎの
    ｋ乗を法とする剰余である復号化認証子データｈ(Ｍ)を
    求め、 この復号化認証子データｈ(Ｍ)と、前記認証対象となる
    認証文データＭをハッシュ化したハッシュ化認証子デー
    タｈ(Ｍ)′が一致していた場合は、一連の認証ないし検
    証過程が正常であったと判定し、 この復号化認証子データｈ(Ｍ)と、前記認証対象となる
    認証文データＭをハッシュ化したハッシュ化認証子デー
    タｈ(Ｍ)′が不一致であった場合は、一連の認証ないし
    検証過程のいずれかに異常があったと判定する、 ことを特徴とするＮ進表現暗号による認証文検証プログ
    ラムを格納した記憶媒体。
  48. 【請求項４８】認証対象となる認証文データＭと、 前記請求項３９、４０、４１、４３、４４、４５のいず
    れか１項に記載の方法または装置で暗号化された暗号化
    認証子ｈ(Ｃ)データと、 それぞれｐとｑとを値とする２つの素数データで構成さ
    れた秘密鍵データ同士の積Ｎを値とする公開鍵データ
    と、 を用いて、前記認証文データＭ及びまたは前記暗号化認
    証子データｈ(Ｃ)が正当であるか否かを判別するＮ進表
    現暗号による認証文検証装置であって、 前記暗号化認証子データｈ(Ｃ)を２乗した値に対して、
    Ｎをｋ乗した数値を法とする剰余である復号化認証子デ
    ータｈ(Ｍ)を生成する認証子復号化手段と、 前記認証文データＭをハッシュ化してハッシュ化認証子
    データｈ(Ｍ)′を生成するハッシュ化手段と、 前記復号化認証子データｈ(Ｍ)と、前記ハッシュ化記認
    証子データｈ(Ｍ)′とを比較し、両者が一致していた場
    合は、一連の認証ないし検証過程が正常であったと判定
    し、両者が不一致であった場合は、一連の認証ないし検
    証過程のいずれかに異常があったと判定する照合判定手
    段と、 を備えたことを特徴とするＮ進表現暗号による認証文検
    証装置。
JP9156903A 1996-08-09 1997-06-13 Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体 Pending JPH1165439A (ja)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP9156903A JPH1165439A (ja) 1996-08-09 1997-06-13 Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体
CA002212664A CA2212664C (en) 1996-08-09 1997-08-08 Secret communication and authentication scheme based on public key cryptosystem using n-adic expansion
EP97113746A EP0823802A3 (en) 1996-08-09 1997-08-08 Secret communication and authentication scheme based on public key cryptosystem using N-adic expansion
US08/907,852 US6259790B1 (en) 1996-08-09 1997-08-08 Secret communication and authentication scheme based on public key cryptosystem using N-adic expansion

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
JP8-211654 1996-08-09
JP21165496 1996-08-09
JP15409597 1997-06-11
JP9-154095 1997-06-11
JP9156903A JPH1165439A (ja) 1996-08-09 1997-06-13 Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体

Publications (1)

Publication Number Publication Date
JPH1165439A true JPH1165439A (ja) 1999-03-05

Family

ID=27320595

Family Applications (1)

Application Number Title Priority Date Filing Date
JP9156903A Pending JPH1165439A (ja) 1996-08-09 1997-06-13 Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体

Country Status (4)

Country Link
US (1) US6259790B1 (ja)
EP (1) EP0823802A3 (ja)
JP (1) JPH1165439A (ja)
CA (1) CA2212664C (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001142396A (ja) * 1999-11-16 2001-05-25 Dainippon Printing Co Ltd 暗号化装置とその方法、暗号復号化装置とその方法および通信システム
JP2005204134A (ja) * 2004-01-16 2005-07-28 Mitsubishi Electric Corp 耐タンパ暗号システム及びメモリ装置及び認証端末及び及びプログラム

Families Citing this family (34)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE69826963T2 (de) * 1997-11-04 2005-11-17 Nippon Telegraph And Telephone Corp. Gerät für die modulare Inversion zur Sicherung von Information
CA2267721C (en) * 1998-03-26 2002-07-30 Nippon Telegraph And Telephone Corporation Scheme for fast realization of encryption, decryption and authentication
US6226618B1 (en) * 1998-08-13 2001-05-01 International Business Machines Corporation Electronic content delivery system
AUPQ439299A0 (en) * 1999-12-01 1999-12-23 Silverbrook Research Pty Ltd Interface system
US7999964B2 (en) 1999-12-01 2011-08-16 Silverbrook Research Pty Ltd Printing on pre-tagged media
US20020051545A1 (en) * 2000-08-14 2002-05-02 Ogilvie John W.L. Encryption multiplexing
JP2002229445A (ja) * 2001-01-30 2002-08-14 Mitsubishi Electric Corp べき乗剰余演算器
FR2821225B1 (fr) * 2001-02-20 2005-02-04 Mobileway Systeme de paiement electronique a distance
JP2003023421A (ja) * 2001-07-09 2003-01-24 C4 Technology Inc 暗号方法、そのプログラム、そのプログラムを記録した記録媒体および暗号装置並びに復号方法および復号装置
JP2003050745A (ja) * 2001-08-07 2003-02-21 Sony Corp 情報処理装置、および情報処理方法、並びにコンピュータ・プログラム
US7237115B1 (en) * 2001-09-26 2007-06-26 Sandia Corporation Authenticating concealed private data while maintaining concealment
JP3818263B2 (ja) * 2003-01-28 2006-09-06 日本電気株式会社 Ａｅｓ暗号処理装置、ａｅｓ復号処理装置、ａｅｓ暗号・復号処理装置、ａｅｓ暗号処理方法、ａｅｓ復号処理方法、および、ａｅｓ暗号・復号処理方法
JP4696449B2 (ja) * 2004-01-09 2011-06-08 ソニー株式会社 暗号化装置およびその方法
US8442219B2 (en) * 2004-03-31 2013-05-14 Jesse Lipson Public key cryptographic methods and systems
JP4728327B2 (ja) * 2004-05-18 2011-07-20 シルバーブルック リサーチ ピーティワイ リミテッド 取引端末
US7725715B2 (en) * 2005-02-24 2010-05-25 Access Business Group International Llc System and method for three-phase data encryption
US7697159B2 (en) 2005-05-09 2010-04-13 Silverbrook Research Pty Ltd Method of using a mobile device to determine movement of a print medium relative to the mobile device
US7284921B2 (en) 2005-05-09 2007-10-23 Silverbrook Research Pty Ltd Mobile device with first and second optical pathways
US7447908B2 (en) * 2005-05-09 2008-11-04 Silverbrook Research Pty Ltd Method of authenticating a print medium offline
US7680512B2 (en) * 2005-05-09 2010-03-16 Silverbrook Research Pty Ltd Method of using a mobile device to print onto a print medium taking into account an orientation of a print medium
US7726764B2 (en) 2005-05-09 2010-06-01 Silverbrook Research Pty Ltd Method of using a mobile device to determine a position of a print medium configured to be printed on by the mobile device
AU2006274486B2 (en) * 2005-07-25 2009-09-17 Silverbrook Research Pty Ltd Product item having coded data identifying a layout
WO2007020566A1 (en) * 2005-08-19 2007-02-22 Nxp B.V. Circuit arrangement for and method of performing an inversion operation in a cryptographic calculation
US7499552B2 (en) * 2006-01-11 2009-03-03 International Business Machines Corporation Cipher method and system for verifying a decryption of an encrypted user data key
US7848516B2 (en) * 2006-01-20 2010-12-07 Chiou-Haun Lee Diffused symmetric encryption/decryption method with asymmetric keys
US7976549B2 (en) * 2006-03-23 2011-07-12 Theken Spine, Llc Instruments for delivering spinal implants
KR20080084480A (ko) * 2007-03-16 2008-09-19 삼성전자주식회사 매개 모듈을 이용한 디바이스간의 상호 인증 방법 및 그시스템
IL185285A0 (en) * 2007-08-14 2008-01-06 Yeda Res & Dev A method and apparatus for implementing a novel one-way hash function on highly constrained devices such as rfid tags
EP2415199B1 (fr) * 2009-03-31 2017-10-18 Koninklijke Philips N.V. Procede pour effectuer une tache cryptographique dans un composant electronique
JP5594034B2 (ja) * 2010-07-30 2014-09-24 ソニー株式会社 認証装置、認証方法、及びプログラム
DE102010040688A1 (de) * 2010-09-14 2012-03-15 Siemens Aktiengesellschaft Verfahren und Vorrichtung zum Authentisieren von Multicast-Nachrichten
WO2017001022A1 (en) * 2015-07-02 2017-01-05 Telefonaktiebolaget Lm Ericsson (Publ) Method for obtaining initial access to a network, and related wireless devices and network nodes
FR3069993B1 (fr) * 2017-08-07 2020-09-18 Maxim Integrated Products Dispositifs et procedes de masquage d'operations de chiffrement rsa
JP6926042B2 (ja) * 2018-09-19 2021-08-25 株式会社東芝 鍵生成装置、鍵生成方法及びプログラム

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2001142396A (ja) * 1999-11-16 2001-05-25 Dainippon Printing Co Ltd 暗号化装置とその方法、暗号復号化装置とその方法および通信システム
JP2005204134A (ja) * 2004-01-16 2005-07-28 Mitsubishi Electric Corp 耐タンパ暗号システム及びメモリ装置及び認証端末及び及びプログラム

Also Published As

Publication number Publication date
EP0823802A2 (en) 1998-02-11
CA2212664A1 (en) 1998-02-09
US6259790B1 (en) 2001-07-10
CA2212664C (en) 2001-08-07
EP0823802A3 (en) 2008-04-09

Similar Documents

Publication Publication Date Title
JPH1165439A (ja) Ｎ進表現暗号による通信および認証方法、ならびにそれらの装置、およびｎ進表現暗号による通信および認証プログラムを格納した記憶媒体
CN110958112B (zh) 密钥产生方法及系统、加密及解密方法、加密通信系统
US6396926B1 (en) Scheme for fast realization of encrytion, decryption and authentication
Jaju et al. A Modified RSA algorithm to enhance security for digital signature
US20100166174A1 (en) Hash functions using elliptic curve cryptography
CN114095181B (zh) 一种基于国密算法的门限环签名方法及系统
CN113711564A (zh) 用于加密数据的计算机实现的方法和系统
US20060083370A1 (en) RSA with personalized secret
CN104168114A (zh) 一种分布式的基于(k,n)门限证书加密方法及系统
CN109474425B (zh) 一种基于多个共享密钥获得任意指定长度派生密钥的方法
CN115804061A (zh) 生成共享私钥
Hodowu et al. An enhancement of data security in cloud computing with an implementation of a two-level cryptographic technique, using AES and ECC algorithm
CN117795901A (zh) 生成数字签名份额
KR20040009766A (ko) 암호 시스템에서 송수신 장치 및 방법
CN116915407A (zh) 基于区块链的电子公证书校验方法及系统
Raut et al. A Comprehensive Review of Cryptographic Algorithms
CN1771687B (zh) 数字证书
CN102064938B (zh) 一种基于多变量与不确定性的公钥加密方法
JP2004246350A (ja) 暗号化装置および復号化装置、並びにこれらを備えた暗号システム、暗号化方法および復号化方法
KR100388059B1 (ko) 비대칭키 암호 알고리즘을 이용한 데이터 암호화 시스템및 그 방법
Pon et al. Dynamic reblocking RSA-based multisignatures scheme for computer and communication networks
Viswanath et al. A secure cryptosystem using the decimal expansion of an Irrational number
Bohli et al. On subliminal channels in deterministic signature schemes
Kumar et al. A comparative analysis of encryption algorithms for better utilization
CN118592008A (zh) 生成共享私钥