JPH0586699B2

JPH0586699B2 -

Info

Publication number: JPH0586699B2
Application number: JP60042052A
Authority: JP
Inventors: Tatsuaki Okamoto; Shoji Myaguchi; Akira Shiraishi; Tsukasa Kawaoka
Original assignee: Nippon Telegraph and Telephone Corp
Current assignee: NTT Inc
Priority date: 1985-03-04
Filing date: 1985-03-04
Publication date: 1993-12-14
Also published as: JPS61200778A

Description

【発明の詳細な説明】「産業上の利用分野」この発明は文書をデイジタル情報として送受信
する通信方式において、文書の作成責任者及び文
書の正当性を受信者及び第三者が検証できるよう
に、文書に署名を付加して送信する署名文書通信
方式に関する。

「従来の技術」文書をデイジタル情報として伝送する場合に、
その文書の一部を変更したり、全く別の内容に変
更したり、あるいは署名者を変更したりすること
は比較的容易であり、しかも受信側ではこれらの
変更があつたことを一般には知ることができな
い。

このような点より送信側で送信デイジタル情報
を処理し、受信側で受信したデイジタル情報の文
書及び署名が正当であることを検証できるように
した方式が提案されている。この方式は署名文書
通信方式と呼ばれている。

従来の署名文書通信方式としては、米国暗号標
準（DES：Data Encryption Standard）に代表
される慣用暗号を用いた方式（S.M.Matyas
“Digital Signatures−An Overiew”Computer
Networka，Vol.3No.２，pp87〜94，1978）及び
RSA法に代表される公開鍵暗号を用いた方式
（R.L.Rivest“AMethod for Obtaining Digital
Signatures and Public−Key Cryptosiptems”
Communications on ACM，Vol.2No.２，pp120
〜126，1978）がある。しかし前者の慣用暗号を
用いた方式は、署名作成及び検証の手続が複雑で
あること、検証側での保存情報量が多くなること
等の欠点がある。一方後者の公開鍵暗号を用いた
方式（以下RSA法という）は安全性、手続きの
簡便さ等の点で最も代表的なものであるが、処理
速度が遅いという欠点がある。この欠点を改善す
るため、データ圧縮を用いた方式、（以下ハイブ
リツド方式という）も提案されているが、（D.W.
Davics“Applying the R.S.A Digital Signature
to Electronic Mail”IEEECOMPUTER Fed.
pp55〜62，1983）この方式は短い文書に対する
署名での処理速度の改善が困難であるという欠点
がある。

この発明の目的は安全性、手続きの簡便さ、署
名の長さは従来のRSA法と同程度であり、しか
も署名の生成、署名の検証を従来のRSA法より
高速度に行うことができる署名文書通信方式を提
供することにある。

「問題点を解決するための手段」この発明によれば従来のRSA法と同様に秘密
情報と公開情報とを用いて署名の作成、証明の検
証を行う。その秘密情報を送信すべき文書作成者
（責任者）Ｄが秘密に保持し、その秘密情報をも
とに公開情報を作成し、その公開情報とこれと対
応する文書作成者（又はその識別コード）とを例
えば登録簿に予め登録して公開しておく。送信側
では文書作成者は乱数と送信すべき文書とを変数
とし、その乱数に関し三次以上となつている合同
多項式と秘密情報とを基本として送信すべき文書
に対応した署名を生成する。その署名と前記文書
とを送信する。これらの処理をすべてデイジタル
信号として行う。また送信で代表して示すが各種
デイジタル情報記憶装置に記憶する場合もある。

受信側では受信した署名及び受信した文書を、
それぞれ前記乱数及び送信すべき文書の代りに用
いた前記合同多項式と前記公開情報とから算出し
た２値の最上位から連続する“０”ビツトの個数
を利用、又はそれと対応する不等式を利用して文
書の正当性及び文書の作成者の正当性を検証す
る。

また送信側では送信する文書と、乱数とを変数
とし、その乱数については二次以上となつている
合同多項式と秘密情報とを基本として送信する文
書と対応した署名を作成し、その署名を文書と共
に送信し、受信側では公開情報より合同多項式を
用いて算出した２値の最上位を除く、任意ビツト
より連続する“０”ビツトの個数を利用、又はそ
れに対応する合同式を利用して受信文書及び署名
者の正当性を検証する。

発明の原理秘密情報として素数ｐ，ｑ（ｐ＞ｑ）を用いる。

この素数ｐ，ｑはRSA法における公開鍵ｎ＝
pqの素数と同様なものである。この素数ｐ，ｑ
をもとに公開情報ｎ，δ，ε，γを作る。これら
はｎ＝p²ｑ，１≦δ≦〓（n^2/3），〓(B)はＢのオー
ダを意味し、ε＝〓（n^1/3），γ＝〓（ｎ／Ｔ）
であり、Ｔは10¹⁰〜10³⁰程度の値である。この秘
密情報ｐ，ｑの保持者Ｄとその公開情報との対応
を予め公開しておく。

署名生成は次のようにして行う。乱数ｘ（１≦
ｘ≦pq−１）を生成し、(1)，(2)式を満足するｗ，
ｖを求める。

Ｚ≦wpq＋vεδ＜Ｚ＋δ ……(1) Ｚ＝−ｇ（ｍ）−｛ｆ（ｘ，ｍ）（modn）｝ ……(2) ｍは送信すべき文書、ｇ（ｍ）はｍに関する任
意の関数、ｆ（ｘ，ｍ）＝_I 〓ⁱ⁼⁰ fi（ｍ）・xⁱ ……(3) Ｉ≧２，fi（ｍ）はｍに関する任意の関数、つ
まりｆ（ｘ，ｍ）（modn）は乱数ｘ、送信すべき
文書ｍを変数とし、ｘに関し二次以上となつてい
る合同多項式であり、modnはｎを法とする演
算、つまりｆ（ｘ，ｍ）の値がｎの整数倍である
場合はゼロであり、０≦ｆ（ｘ，ｍ）（modn）＜
ｎの値しかとらない。ｗ，ｖを求める手法は後で
述べる。なお、ｗは以下の条件を満足するものと
し、この条件を満足しない場合は、後で述べる
ｗ，ｖを求める手法を再度実行し、この条件を満
足するまでくり返す。

−（ｆ（ｘ，ｍ）（modn））／（pq） ≦ｗ＜ｐ−（ｆ（ｘ，ｍ）（modn））／（pq）上記条件のｗを得ると、ｙ＝ｗ／f′（ｘ，ｍ）（modp） f′（ｘ，ｍ）＝df（ｘ，ｍ）／dx＝_I 〓ⁱ⁼⁰ fi（ｍ）・ｉ・x^i-1 ……(4) を演算し、更にｓ＝ｘ＋ypq ……(5) を演算してｓを送信すべき文書ｍと対応した署名
とする。

この文書ｍと署名ｓとを送信する。

受信側では受信した文書ｍ及びを署名ｓと、そ
の送信文書の署名者Ｄの公開情報ｎ，δ，εとを
用いて(6)式を演算して検証する。

〓ｇ（ｍ）＋｛ｆ（ｓ，ｍ）（modn）｝／δ〓＝０（modε） ……(6) 〓Ａ〓はＡの以下の最大の整数である。(6)式は〓
Ａ〓（modε）がゼロを意味している。

更にγ≦ｓ≦ｎ−γ ……(7) の比較演算を行い、ｓが(7)式を満足しない場合は
(6)式の検証結果を無視する。このことは署名ｓが
γより短かいと第三者が署名ｓを偽造し易いもの
となるためである。受信側では前記検証を行うた
め前記(3)式の合同多項式と関数ｇ（ｎ）を予め知
つている。また署名者がＤであることは誰れでも
知ることができるように署名者Ｄを示す情報をも
送信文書ｍと共に送るか、何らかの方法により受
信した時に、受信側では署名者Ｄからの受信であ
ることを知つて、前記検証を行い、つまりその受
信文書が署名者Ｄからのものと間違いがなく、か
つその文書は変更されていないことを検証する。

(6)式の検証の証明 (5)式、(3)式の関係をｆ（ｓ，ｍ）（modn）に代
入すると次のようになる。

ｆ（ｓ，ｍ）（modn）＝ｆ（ｘ＋ypq，ｍ）（modn）＝_I 〓ⁱ⁼⁰ fi（ｍ）・（ｘ＋ypq）ⁱ（modn）（法ｎの演算であるためｎ＝p²ｑを含む項はす
べてゼロとなるから）＝_I 〓ⁱ⁼⁰ fi（ｍ）xⁱ＋_I 〓ⁱ⁼⁰ fi（ｍ）・ｉ・x^i-1 ・ypq（modn）（(3)式、(4)式から）＝ｆ（ｘ，ｍ）＋f′（ｘ，ｍ）・ypq（modn）
……(8) (4)式よりf′（ｘ，ｍ）・ｙ＝ｗ（modp）となり、
その両辺にpqを掛算して、 f′（ｘ，ｍ）−ypq＝wpq（modn）となる。これを(8)式に代入すると、ｆ（ｓ，ｍ）（modn）＝ｆ（ｘ，ｍ）＋wpq（modn）＝｛ｆ（ｘ，ｍ）（modn）｝＋wpq ……(9) となる。一方(1)式を次に変形するｚ−vεδ≦wpq＜ｚ−vεδ＋δ この各項にｇ（ｍ）＋｛ｆ（ｘ，ｍ）（modn）｝を
加えwpqについて(9)式の関係を用いると次式とな
る。

ｇ（ｍ）＋｛ｆ（ｘ，ｍ）（modn）｝＋ｚ−vεδ ≦ｇ（ｍ）＋｛ｆ（ｓ，ｍ）・（modn）｝＜ｇ（ｍ）＋｛ｆ（ｘ，ｍ）・（modn）｝＋ｚ−vεδ＋δ この式に(2)式の関係を代入すると、 −vεδ≦ｇ（ｍ）＋｛ｆ（ｓ，ｍ）（modn）｝＜−vεδ＋δ となり、その両辺をδで割ると −vε≦ｇ（ｍ）＋｛ｆ（ｓ，ｍ）（modn）｝／δ ＜−vε＋１となる。この式の中辺は−vεと−vε＋１との間
にあるから、その小数点以下の最大の整数は〓ｇ（ｍ）＋｛ｆ（ｓ，ｍ）（modn）｝／δ〓＝−v
ε となる。従つてこれに対し法εの演算を行うと、〓ｇ（ｍ）＋｛ｆ（ｓ，ｍ）（modn）｝／δ〓＝０（modε）となり、(6)式の検証結果が０になれば、その署名
ｓは公開情報のｎ，δ，ε，γと対応する署名者
Ｄによるものであり、かつ受信文書も変更されて
いないものであるとその正当性が検証される。つ
まり前記署名ｓを作ることができる人は、その秘
密情報pqをもつている人Ｄのみであり、しかも
その署名ｓは送信すべき文書と対応して作つてい
るため、異なる秘密情報が用いられたり、送信す
べき文書が変更されると、前記関係が得られなく
なり、つまり(6)式の検証結果が０にならない。

「実施例」まず三次以上の合同多項式を基本に署名作成を
行い、２値の最上位より連続する“０”ビツトの
個数、もしくはそれに対応する不等式を用いて署
名検証を行う方式、つまり第１の発明について説
明する。この例はｆ（ｘ，ｍ）＝ｆ(x)，（ｆ(x)はｘ
に関する３次以上の合同多項式）、ｇ（ｍ）＝Ｍ＝
ｈ（ｍ）（Ｍは文書ｍをデータ圧縮したもの）δ＝
〓（n^2/3）とした場合である。

最初に送信者（署名作成者）は、通信に先立つ
て以下の情報を生成する。

既に知られている素数生成アルゴリズム（例え
ば、和田秀男著「高速乗算法と素数判定法」上智
大学数学講究録No.15）を用いて、それぞれ例えば
10進50桁〜100桁程度の素数ｐ，ｑを生成する。
ただしｐ＞ｑとする（ｐ−ｑの桁数は同程度とす
る）。

更に以下の式によりｎ，δ，γを生成する。

ｎ＝P²ｑ δ＝〓（n^2/3） γ＝〓（ｎ／Ｔ）ここでＴは10¹⁰〜10³⁰程度の値、以上の手続き
で生成した情報のうち、送信者Ｄが秘密に保持す
る秘密情報はｐ，ｑであり、公開簿に登録する公
開情報はｎ，δ，γである。なお公開簿にはｎ，
δ，γを送信者Ｄの識別番号（ID）と共に登録
しておく。以上の手続きは最初に一度行えば基本
的に以降行う必要はない。

次に第１図に従つて第１の発明による署名作成
手順を説明する。まず設定器１１，１２にそれぞ
れ前記ｐ，ｑが設定され、乗算器１３でpqの乗
算が行われ、また乗算器１４でｎ＝p²ｑの乗算が
行われる。乗算器１４の代りに設定器にｎを設定
してもよい。文書源１５から送信する文書ｍがデ
イジタル情報として発生される。この例では圧縮
器１６で文書ｍはデータ圧縮されて、正整数Ｍと
される。０≦Ｍ≦ｎ−１とする。

圧縮器１６は例えば第２図に示すように構成さ
れる。レジスタ１７に入力された文書ｍは次式を
満足するようにm₁，m₂……m_kに分割される。

０≦m_i≦ｎ−１（ｉ＝１，２，……ｋ）次の以下の関係から圧縮文書Ｍ＝ｈ（ｍ）を定
める。

C₀＝I₀ C_i＝（m_i○＋C_i-1）²（modn）Ｍ＝ｈ（ｍ）＝C_k○＋I₁）²（modn） I₀，I₁はシステム又は送信者により定められる
値である。この圧縮文書Ｍ＝ｈ（ｍ）を得るには、
各分割した文書m₁……m_hはレジスタ１７よりそ
れぞれ排他的倫理和回路1₁……1_kへ供給され、各
排他的論理和回路1₁……1_kの出力は法ｎの合同二
乗演算器2₁……2_kへ供給され、これら合同二乗演
算器2₁……2_kの各出力C₁……Chはそれぞれ排他
的論理和回路2₂……2_k+1へ供給される。排他的論
理和回路1₁にはC₀としてI₀が与えられ、排他的論
理和回路1_k+1にはI₁が与えられ、その出力は法ｎ
の合同二乗演算器2_k+1で法ｎの二乗演算が行わ
れ、その出力に圧縮された文書Ｍ＝ｈ（ｍ）が得
られる。

第１図の説明から戻る。送信側は乱数発生器１
８より次の条件を満足する乱数ｘを得る。

１≦ｘ≦pq−１（ただしｘはｎと互いに素な整数とする。）ここではｆ（ｘ，ｍ）＝f₁(x)とされ、(10)式で表わ
され、システムもしくは各送信者によつて事前に
定められる公開関数とする。

f₁(x)＝_I 〓ⁱ⁼⁰ giXⁱ（ｉ＝１，２…Ｉ） ……(10) ０≦gi≦ｎ−１ gi：整数ここでＩ≧３とする（gi≠０）。乱数ｘに対し
て（f₁(x)（modn））の演算を合同多項式演算器１
９を用いて行い、その演算結果と圧縮文書Ｍとか
ら減算器２１を用いてＺ＝Ｍ−（f₁(x)（modn）） ……(11) を求める。そのＺを除算器２２によりpqで割算
し、その割算結果は切上げ演算器２３を用いてＷ＝〓Ｚ／（pq）〓 ……(12) （ここで〓Ａ〓はＡ以上の最小の整数である。）
が求められる。一方、乱数ｘに対して（f1´(x)
（modp））を出力する合同多項式演算器２４で演
算し、その結果でＷを合同除算器２５において割
算し、ｙ＝Ｗ／（f1´(x)（modp））（modp）を求める。
ここで f1´(x)＝_I 〓ⁱ⁼⁰ ig_iX^i-1 ……(13) また合同除算器２５は拡張ユークリツド互除法
を用いて構成される。拡張ユークリツド互除法演
算アルゴリズムについては、D.Knuth氏著“The
Art of Computer Progamming，Vol.2”
AddisonWeslay（1969）に詳述されている。

この除算結果ｙは乗算器２６でpqと乗算され、
その乗算結果に対し、加算器２７で乱数ｘが加算
されてｓ＝ｘ＋ypq ……(14) を求める。

以上により求められた署名ｓを文書ｍ、送信者
の識別番号（ID）と共に受信側へ送信する。

次に第３図に従つて（ｍ，ｓ）を受け取つた受
信側の検証手順を説明する。まず受信側では受信
した識別番号IDより公開簿を参照してその送信
者の公開情報（ｎ，δ，γ）を読み取り、それぞ
れ設定器２８，２９，３１に設定する。次に受信
署名ｓに対し合同多項式演算器３２を用いて（f₁
(s)（modn））を求める。また受信文書ｍに対し
圧縮器３３でデータ圧縮を行つて圧縮文書Ｍ＝ｈ
（ｍ）を求める。これらf₁(s)（modn）とＭ＝ｈ
（ｍ）とδとを用いて比較器３４で以下の不等式
が成立するかどうかを検証し、成立すれば肯定と
する。

Ｍ≦f₁(s)（modn）＜Ｍ＋δ ……(15) 一方、減算器３５でｎ−γを求め、比較器３６
によりｓとγ及びｎ−γとを比較し γ≦ｓ≦ｎ−γ ……(16) であれば肯定とする。比較器３４，３６の出力が
両方共に肯定の場合は受信した（ｍ，ｓ）公開簿
に（ｎ，δ，γ）を登録した者によつて正しく作
成されたものであるとする。

（15）式の検証式の各辺からＭを差引き、δで
割算すると、０≦−Ｍ＋f₁(s)（modn）／δ＜１となり、その中辺の値以下の最大整数をとると、〓−Ｍ＋f₁(s)（modn）／δ〓＝０ ……(17) となり、この式は(6)式の検証式と一致し、（15）
式の検証が正しいことが理解される。

更にこの実施例において（15）式及び（16）式
の検証に代えて、バイナリ値（12進数）の最上位
より連続するビツト“０”の個数で検証できるこ
とを示す。つまり公開情報δ，γを以下のように
このべき乗の形で定義する。

δ＝2^d＝〓（^2/3） γ＝2^r＝〓（ｎ／Ｔ）このときこれらと（17）式とから検証は以下の
バイナリ値により行えばよいことがわかる。つま
り（18）式（19）式が共に成立すれば受信（ｍ，
Ｓ）を正当とみなす。

〔（f₁(s)（modn））−ｈ（ｍ）〕^d＝≠……(18) 〔ｓ〕^r≠０／，〔ｎ−ｓ〕^r≠０／ ……(19) ここで〔Ａ〕^dはバイナリ表現されたＡの最上位
より連続する（｜ｎ｜−ｄ）ビツトを意味する。
（｜ｎ｜＝〓1og₂ｎ〓）、また〓はすべてが“０”
より構成される任意の長さのビツト列を意味す
る。

以上第１発明に対応する実施例の詳細について
述べたが、多項式f₁(x)に関する２次式とし、他に
ついては前記実施例と同様にすると、特許請求の
範囲３に示したものの実施例が得られる。

第２実施例次に二次以上の合同多項式を基本に署名作成を
行い、２値の最上位を除く任意のビツトより連続
する“０”ビツトの個数等、もしくはそれに対応
する等式等を用いて署名検証を行う方式について
説明する。これは第２の発明の実施例であつて、
ｆ（ｘ，ｍ）＝ｆ(x)とし、（ｆ(x)はｘについての二
次以上の合同多項式）ｙ（Ｍ）＝−Ｍとした場合で
ある。

10進50桁〜100桁程度の素数ｐ，ｑを選択し、以下の式により正整数ｎ，δ，εを生成する。

ｎ＝p₂ｑ１≦δ＜pq ε＝〓（n^1/3） γ＝〓（ｎ／Ｔ）ここでＴは10¹⁰〜10³⁰程度の値であるが、関数
f₂の次数が十分に大きい場合（n^1/t＜１；ｔはf₂の
次数）、γ＝１として良い。

以上の手続きで生成した情報のうち、送信者が
秘密に保持する秘密情報はｐ，ｑであり、公開簿
に登録する公開情報はｎ，δ，ε，γである。な
お公開簿にはｎ，δ，ε，γを送信者の識別番号
（ID）と共に登録しておく。以上の手続きは最初
に一度行えば基本的に以降行う必要はない。

次に第４図に従つて、この第２の発明の実施例
における署名作成手順を説明する。第４図で第１
図と対応する部分には同一符号を付けてある。ま
ず送信者は署名を付けたい文書ｍに対し、圧縮器
１６でデータ圧縮を行い、正整数Ｍ＝ｎ（ｍ）を
求める。乱数発生器１８より次の各条件を満足す
る乱数ｘを得る。１≦ｘ≦pq−１，ｘはｍと互
に素な整数。さらに関数f₂をシステムもしくは各
送信者により事前に定められる公開関数とする。

ｆ(x)＝_I 〓ⁱ⁼⁰ giXⁱ （ｉ＝１，２…Ｉ）０≦gi≦ｎ−１ gi：整数ここでＩ≧２とする（g_I≠０）。

乱数ｘに対して（f₂(x)（（modn））を出力する
合同多項式演算器１９及び減算器２１を用いてＺ＝Ｍ−（f₂(x)（modn）） ……(20) を求める。このＺと乗算器１３のpqと、設定器
３７のεと、設定εと設定器３８のδとをｗ演算
器３９に入力し、（21）式を満足する整数ｗ，ｖ
を求める。

Ｚ≦wpq＋vεδ＜Ｚ＋δ ……(21) このｗ，ｖを求めるアルゴリズムの例を第５図
に示す。このアルゴリズムはＡ，Ｂの最大公約数
を求めるイクステンデイツドユークリフドアルゴ
リズムを利用して得たものである。まずステツプ
S₁でpqとδの大きいものをＡとし、小さいもの
をＢとし、ＺをＣとし、更にa₁，a₂をそれぞれ
１，０とし、b₁，b₂をそれぞれ０，１とし、c₁，
c₂をそれぞれ０，０とする。

ステツプS₂でＡ，Ｂの大小を判定し、Ａ＞Ｂな
らばステツプS₃で〓Ａ／Ｂ〓をＫとし、〓Ｃ／Ｂ
〓をＬとする。a₁−Kb₁を次のa₁とし、a₂−Kb₂
を次のa₂とし、これらのことを（a₁，a₂）←
（a₁，a₂）−Ｋ（b₁，b₂）で表示する。同様に（c₁，
c₂）＋Ｌ（b₁，b₂）をそれぞれ求めて次のc₁，c₂と
し、更にＡ−KBを次のＡ，Ｃ−LBを次のＣと
する。一方ステツプS₂でＢ＞ＡならばステツプS₄
で〓Ｂ／Ａ〓をＫ，〓Ｃ／Ａ〓をＬとし、これら
を用いて（b₁，b₂）−Ｋ（a₁，a₂）をそれぞれ次の
（b₁，b₂）とし、（c₁，c₂）＋Ｌ（a₁，a₂）をそれぞ
れ次の（c₁，c₂）とし、更にＢ−KAを次のＢ，
Ｃ−LAを次のＣとする。ステツプS₃又はS₄の次
にステツプS₅でＡ，Ｂの大きいものとδとを比較
し、等しいかδの方が小さい場合はステツプS₂に
戻り、δの方が大きい場合はステツプS₆でＡとＢ
とを比較する。Ａ＞ＢならばステツプS₇でpqと
εδとを比較し、pq＞εδならばステツプS₈でa₁＋c₁
をｗとし、a₂＋c₂をｖとし、pq＜εδならばステツ
プS₉でa₂＋c₂をｗとし、a₁＋c₁をｖとする。ステ
ツプS₆でＢ＞ＡならばステツプS₁₀でpq＜εδとを
比較し、pq＜εδならばステツプS₁₁でb₁＋c₁をｗ
とし、b₂＋c₂をｖとし、pq＜εδならばb₂＋c₂をｗ
とし、b₁＋c₁をｖとする。

第４図においてこのようにしてｗ演算器３９よ
り得られたｗ、及び乱数ｘに対し（f2´(x)
（modp））を出力する合同多項式演算器２４、及
び合同除算器２５を用いて、ｙ＝ｗ／（f2´(x)（modp））（modp）を求める。
ここで f2´(x)＝_I 〓ⁱ⁼⁰ ｉ・gi・X^i-1 ……(22) 更に乗算器２６、加算器２７を用いて前述と同
様に、ｓ＝ｘ＋ypq ……(23) を求める。

以上により求めたれた署名ｓを文書ｍ、送信者
の識別番号（ID）と共に受信側へ送信する。

次に第６図に従つて（ｍ，ｓ）を受け取つた受
信側の検証手順を説明する。まず受信側では受信
した識別番号IDより公開簿からその送信者の公
開情報（ｎ，δ，ε，γ）を読み取り、それぞれ
設定器２８，２９，３１に設定する。次に受信し
た署名ｓに対し合同多項式演算器３２を用いて
（f₂(s)（modn））を求める。また受信文書ｍに対
し、圧縮器３３でデータ圧縮を行い、圧縮文書Ｍ
＝ｈ（ｍ）を求める。減算器４１、除算器４２、
切り捨て演算器４３、剰余演算器４４、比較器４
５を用いて以下の（24）式が成立するかどうかを
検証し、成立すれば肯定とする。

〓（f₂(s)（modn））−Ｍ／δ〓＝０（modε）……(2
4) （ここで〓Ａ〓はＡ以下の最大の整数である。）
また減算器３５、比較器３６によりｓの値とγ，
ｎ−γの値とを比較し、 γ≦ｓ≦ｎ−γ ……(25) であれば肯定とする。比較器３６，４５が両方共
肯定の場合、受信（ｍ，ｓ）は公開簿に公開情報
（ｎ，δ，ε，γ）を登録した者によつて正しく
作成されたものとする。

次に（24）式の検証と代えて、バイナリ値の最
上位を除く任意のビツトから連続するビツト
“０”の個数で検証できることを示す。なお（25）
式の検証に対応する方式は前に述べたものと同じ
であり、（19）式の検証に公開情報δ，εを以下
のような２のべき乗の形で定義する。

１≦δ＝2^d＜pq ε＝2^e＝〓（n^1/3）このときこれらと（24）式とから検証は以下の
バイナリ値により行えばよいことが理解される。
つまり（26）式が成立すれば（24）式が成立する
ことと同等とみなす。この（26）式と（19）式と
が共に成立すれば受信（ｓ，ｍ）を正当とみな
す。

〔f₂(s)（modn））−ｈ（ｍ）〕^d _e＝０／ ……(26) ここで〔Ａ〕^dはバイナリ表現されたＡの下位か
ら数えて（ｄ＋１）ビツト目より連続するｅビツ
トを意味する。

「発明の効果」以上説明したようにこの発明によれば、署名作
成で要する演算量で主なものは、データ圧縮１
回、合同多項式演算１回、切り捨て除算１回もし
くはｗ演算器３９の演算（サイズがｐのオーダの
ユークリツト互除法以下の演算量）１回、合同除
算（サイズがｐのオーダのユークリツド互除法と
同等の演算量）１回であり、署名検証で要する演
算量で主なものは、データ圧縮１回、合同多項式
演算１回、切り捨て除算１回（第６図で説明した
方式のみ）であり、合同多項式の次数をRSA法
の次数に比べ十分小さくすれば、RSA法に比べ
高速な署名作成／検証が可能になるという利点が
ある。例えばRSA法の次数は10²⁰⁰程度であるの
に対し、この発明の合同多項式の次数を10²程度
以下にすれば、ほぼ100倍程度以上高速な処理が
見込まれる。

【図面の簡単な説明】

第１図は第１発明における署名作成手順の構成
例を示すブロツク図、第２図は圧縮器１６の構成
例を示すブロツク図、第３図は第１発明における
署名検証手順の構成例を示すブロツク図、第４図
は第２発明における署名作成手順の構成例を示す
ブロツク図、第５図はｗ演算器３９での演算手順
の例を示す流れ図、第６図は第２図発明における
署名検証手順の構成例を示すブロツク図である。１６，３３……圧縮器、１８……乱数発生器、
１９，２４，３２……合同多項式演算器、２１，
３５，４１……減算器、２２，４２……除算器、
２３……切り上げ演算器、２５……合同除算器、
２６……乗算器、２７……加算器、３４，３６，
４５……比較器、３９……ｗ演算器、４３……切
り捨て演算器、４４……剰余演算器。

Claims

【特許請求の範囲】１送信側で素数ｐ，ｑ（ｐ＞ｑ）を秘密情報と
して用意し、これら素数ｐ，ｑを用いて、公開情
報ｎ＝p²，ｑ，δ（１≦δ≦〓（n^2/3），〓(B)はＢ
のオーダを意味する）、γ＝〓（ｎ／Ｔ）（Ｔは
10¹⁰〜10³⁰程度の値）を作り、これら公開情報
ｎ，δ，γを送信者Ｄの識別番号（ID）と共に
公開簿に登録しておき、乱数ｘ（１≦ｘ≦pq−１，ｘはｎと互いに素な
整数）を生成し、その乱数ｘに対してｆ(x)
（modn）（ｆ(x)＝_I 〓ⁱ⁼⁰ gi xⁱ（ｉ＝１，２，…Ｉ），０
＜gi≦ｎ−１，giは整数Ｉ≧３）を演算し、その演算結果と送信すべき文書ｍとの差Ｚ＝ｍ
−（ｆ(x)（modn））を求め、そのＺをpqで割算し、その割算結果を切り上
げてＷ＝「Ｚ／（pq）」を求め、上記乱数ｘに対し、f′(x)modp（f′(x)＝_I 〓ⁱ⁼⁰ ｉ・
gi・x^i-1）を演算し、その演算結果で上記Ｗを割
算し、この演算結果ｙと上記pqとを乗算し、こ
れに乱数ｘを加算して署名ｓとし、この署名ｓと上記文書ｍと、上記識別番号ID
とを送信し、受信側で受信した上記識別番号IDよりその公
開情報ｎ，δ，γを上記公開簿より求め、受信し
た上記署名ｓに対し、ｆ(s)（modn）を演算し、その演算結果と、上記文書ｍと上記δとを用い
てｍ≦ｆ(s)（modn）＜ｍ＋δが成立するかどう
かを検証し、上記ｎと上記γと、上記署名ｓとを用いてγ≦
ｓ≦ｎ−γが成立するかどうかを検証し、上記両検証が共に成立した場合に上記受信した
ｍ，ｓは上記公開簿に（ｎ，δ，γ）を登録した
者によつて作成されたものとする署名文書通信方
式。２送信側で素数Ｐ，ｑ（ｐ＞ｑ）を秘密情報と
して用意し、これら素数ｐ，ｑを用いて公開情報
ｎ＝p²，ｑ，δ＝2^d＝〓（n^2/3），γ＝2^r＝〓
（ｎ／Ｔ）（Ｔは10¹⁰〜10³⁰程度の値）を作り、こ
れら公開情報ｎ，δ，γを送信者Ｄの識別番号
（ID）と共に公開簿に登録しておき、乱数ｘ（１≦ｘ≦pq−１，ｘはｎと互いに素な
整数）を生成し、その乱数ｘに対してｆ(x)
（modn）（ｆ(x)＝_I 〓ⁱ⁼⁰ gi xⁱ，ｉ＝１，２，…Ｉ，０
＜gi≦ｎ−１，giは整数Ｉ≧３）を演算し、その演算結果と送信すべき文書ｍとの差Ｚ＝ｍ
−（ｆ(x)（modn））を求め、そのＺをpqで割算し、その割算結果を切り上
げてＷ＝「Ｚ／（pq）」を求め、上記乱数ｘに対し、f′(x)modp（f′(x)＝_I 〓ⁱ⁼⁰ ｉ・
gi・x^i-1）を演算し、その演算結果で上記Ｗを割
算し、この演算結果ｙと上記pqとを乗算し、こ
れに乱数ｘを加算して署名ｓとし、この署名ｓと上記文書ｍと、上記識別番号ID
とを送信し、受信側で受信した上記識別番号IDよりその公
開情報ｎ，δ，γを上記公開簿より求め、受信し
た上記署名ｓに対し、ｆ(s)（modn）を演算し、その演算結果と、上記受信文書ｍと上記受信署
名ｓと、上記ｄと、上記ｒとを用いて、［（ｆ(s)
（modn））−ｍ］^d＝０／，［Ｓ］^r＝０／，［ｎ−ｓ］
^r≠０／
（［Ａ］ ^dバイナリで表現されたＡの最上位より連
続する（｜ｎ｜−ｄ）ビツトを意味し、｜ｎ｜＝
「1og₂ｎ」，０／はすべて“０”より構成される任意
の長さのビツト列を意味する）が共に成立するか
どうかを検証し、共に成立した場合に受信した
ｍ，ｓは上記公開簿に（ｎ，δ，γ）を登録した
者によつて作成されたものとする署名文書通信方
式。３送信側で素数ｐ，ｑ（ｐ＞ｑ）を秘密の情報
として用意し、これら素数を用いて、公開情報ｎ
＝p²ｑ，δ（１≦δ＜pq），ε＝〓（n^1/3），γ＝
〓θ（ｎ／Ｔ）（Ｔは10¹⁰〜10³⁰程度の値）を作
り、これら公開情報ｎ，δ，ε，γを送信者Ｄの
識別番号（ID）と共に公開簿に登録しておき、乱数ｘ（１≦ｘ≦pq−１，ｘはｎ送信すべき文
書と互いに素な整数）を生成し、その乱数ｘに対
してｆ(x)（modn）（ｆ(x)＝_I 〓ⁱ⁼⁰ gi xⁱ，ｉ＝１，２，
…Ｉ，０＜gi≦ｎ−１，giは整数Ｉ≧２）を演算
し、その演算結果と上記送信すべき文書ｍとの差Ｚ
＝ｍ−（ｆ(x)（modn）を求め、そのＺと、上記
pqと、上記εと、上記δとからＺ≦wpq＋vεδ＜
Ｚ＋δを満足する整数ｗ，ｖを求め、上記乱数ｘに対し、f′(x)（modp）（f′(x)＝_I 〓ⁱ⁼⁰
ｉ・gi・x^i-1）を演算し、この演算結果で上記Ｗ
を割算してｙを求め、このｙに上記pqを掛算し、上記乱数ｘと加算
して署名ｓを求め、この署名ｓと上記文書ｍと、
上記識別番号IDとを送信し、受信側で受信した識別番号IDにより上記公開
簿からその公開情報ｎ，δ，γを求め、受信した
署名ｓに対しｆ(s)（modn）を演算し、その演算結果と、受信した文書ｍと、上記δ
と、上記εとを用いて〓（ｆ(s)（mod ｎ））−ｍ／δ〓＝０（modε）（〓Ａ」はＡ以下の最大整数）が成立するかどうかを
検証し、上記受信署名ｓと、上記γと上記ｎとか
らγ≦ｓ≦ｎ−γが成立するかどうかを検証し、
これら両検証が同時に成立した場合に、上記受信
したｓ，ｍは上記公開簿の公開情報ｎ，δ，ε，
γを登録した者によつて作成されたものとする署
名文書通信方式。４送信側で素数ｐ，ｑ（ｐ＞ｑ）を秘密の情報
として用意し、これら素数を用いて、公開情報ｎ
＝p²ｑ，δ＝2^d（１≦δ＜pq），ε＝2^e＝〓
（n^1/3），γ＝2^r＝〓（ｎ／Ｔ）（Ｔは10¹⁰〜10³⁰程
度の値）を作り、これら公開情報ｎ，δ，ε，γ
を送信者Ｄの識別番号IDと共に公開簿に登録し
ておき、乱数ｘ（１≦ｘ≦pq−１，ｘは送信すべき文書
ｍと互いに素な整数）を生成し、その乱数ｘに対
してｆ(x)（modn）（ｆ(x)＝_I 〓ⁱ⁼⁰ gixⁱ，ｉ＝１，２，
…Ｉ，０＜gi≦ｎ−１，giは整数、Ｉ≧２）を演
算し、その演算結果と上記送信すべき文書ｍとの差Ｚ
＝ｍ−（ｆ(x)（modn）を求め、そのＺと、上記
pqと、上記εと、上記δとからＺ≦wpq＋vεδ＜
Ｚ＋δを満足する整数ｗ，ｖを求め、上記乱数ｘに対しf′(x)（modp）（f′(x)＝_I 〓ⁱ⁼⁰ ｉ・
gi・x^i-1）を演算し、この演算結果で上記Ｗを割
算してｙを求め、このｙに上記pqを掛算し、上記乱数ｘと加算
して署名ｓを求め、この署名ｓと上記文書ｍと上
記識別番号IDとを送信し、受信側で受信した識別番号IDにより上記公開
簿からその公開情報ｎ，δ，γを求め、受信した
署名ｓに対しｆ(s)（modn）を演算し、その演算結果と、受信文書ｍと、上記ｄと、上
記ｅと、上記ｒとから、［（ｆ(s)（modn））−ｍ］^d _e
＝０／，［Ｓ］^r≠０／，［ｎ−ｓ］^r≠０／（［Ａ］^d _eはバイ
ナリ表現されたＡの下位から数えて（ｄ＋１）ビ
ツト目より連続するｅビツトを意味し、０／はすべ
てが“０”より構成される任意の長さのビツト列
を意味する）が同時に成立するかどうかを検証
し、同時に成立した場合に上記受信したｓ，ｍは
上記公開簿の公開情報ｎ，δ，ε，γを登録した
者によつて作成されたものとする署名文書通信方
式。