【事件の表示】
　平成　５年特許願第　５９５６５号「高速ベキ乗剰余演算法を用いたＲＳＡ暗号方式による暗号化装置及び復号装置」拒絶査定に対する審判事件［平成　８年１０月　１日出願公開、特開平　８−２５４９４９］について、次のとおり審決する。
【結　論】
　本件審判の請求は、成り立たない。
【理　由】
１．手続の経緯・本願発明の要旨
　本願は、平成５年２月２３日の出願であって、その請求項１，２に係る発明（以下、「本願発明１，２」という。）は、平成９年１１月２７日付け手続補正書によって補正された明細書及び図面の記載からみて、その特許請求の範囲の請求項１，２に記載されたとおりの、
　「【請求項１】下記（迅速計算方式）で示されるＲＳＡ暗号方式の暗号化装置内のＭｅｍｏｄ　Ｒｘ−ｙ及び復号装置内のＣｄｍｏｄ　Ｒｘ−ｙの演算を実行する際に、通常の指数乗算法を使用して、該指数乗算法の第ｉステップのＣｉ２　ｍｏｄ　Ｒｘ−ｙのベキ乗剰余演算をｙにｙ＜Ｒｘ／２の制限を加え、指数演算法で使用される第ｉステップにおける値Ｃｉをｎを超える値のまま次のステップで使用するにもかかわらず、Ｃｉ値を或る桁数以下に制限することが可能となることによって、従来の除数の桁数に比例した処理時間を要する除算を使用することなく、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を２回繰り返し実行することによって、上記のベキ乗剰余演算を高速処理すると同時に公開鍵をＲ進表現で公開する場合、連続するＲ−１以外のランダムな数字の部分、即ち、公開鍵の下位の数字部分のみを公開すればよく、ｘ／２桁以下の小さなサイズの公開鍵が使用可能となり、鍵管理メモリの節約及び該公開鍵が暗号化装置又は復号装置に手入力するという利便性を有する簡易な鍵管理を可能ならしめることを特徴とする下記高速ベキ乗剰余回路（１）で示される回路で構成されてなる高速ベキ乗剰余演算法を使用したＲＳＡ暗号方式を用いた暗号化装置及び復号装置。
（迅速計算方式）
ここに、Ｍ：平文（メッセージ）
　　　　ｅ：公開鍵
　　　　Ｒｘ−ｙ：公開鍵、ｎ〔Ｒ，ｘ（ｎの桁数），ｙは小さくない整数〕
　　　　Ｃ：暗号文
　　　　ｄ：秘密鍵
　　　　Ｃｉ：指数演算法で使用される第ｉステップにおける値
　
　　　　Ｃｉ（１）：Ｃｉ２のＲｘ未満の部分の値
　
　　　　Ｃｉ（２）：Ｃｉ２のＲｘ以上の部分をＲｘで割った値
を示す。
　【請求項２】下記（迅速計算方式）で示されるＲＳＡ暗号方式の暗号化装置内のＭｅｍｏｄ　Ｒｘ−ｙ及び復号装置内のＣｄｍｏｄ　Ｒｘ−ｙなる演算を実行する際、通常の指数乗算法を使用して、該指数乗算処理の第ｉステップのＣｉ２　ｍｏｄ　Ｒｘ−ｙなるベキ乗剰余演算をｙの桁数Ｙについて、
整数を表す。）指数演算法で使用される第ｉステップにおける値Ｃｉをｎを超える値のまま次のステップで使用するにもかかわらず、Ｃｉ値を或る桁数以下に制限することが可能となることによって、従来の除数の桁数に比例し
　
た処理時間を要する除算を使用することなく、Ｃｉ２＝Ｃｉ（３）・ｙ２＋
Ｃｉ（２）・ｙ＋Ｃｉ（１）なる形の演算式を１回実行することで、上記ベキ乗剰余演算を高速処理すると同時に公開鍵をＲ進表現で公開する場合、連続するＲ−１以外のランダムな数字の部分、即ち、公開鍵の下位の数字部分のみを公開すればよく、Ｙ桁以下の小さなサイズの公開鍵が使用可能となり、鍵管理メモリの節約及び該公開鍵が暗号化装置又は復号装置に手入力するという利便性を有する簡易な鍵管理を可能ならしめることを特徴とする下記「高速ベキ乗剰余回路（２）」で示される回路で構成されてなる高速ベキ乗剰余演算法を使用したＲＳＡ暗号方式を用いた暗号化装置及び復号装置。
（迅速計算方式）
ここに、Ｍ，ｅ，Ｒｘ−ｙ，Ｃ，ｄ，Ｃｉは請求項１の場合と同一である。
　
　　　　Ｃｉ（２）：Ｃｉ２のＲｘ以上Ｒ２ｘ未満の部分をＲｘで割った値
　
　　　　Ｃｉ（３）：Ｃｉ２のＲ２ｘ以上の部分をＲ２ｘで割った値
を示す。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　」
にあるものと認める。
　
２．引用例
　これに対して、原査定の拒絶の理由に引用された「佐竹賢治，笠原正雄「高速アルゴリズムを用いたＲＳＡ暗号方式」情報処理学会研究報告，Ｖｏｌ．９２，Ｎｏ．９４（９２−ＡＬ−３０），１９９２年１１月，ｐ．１５３〜１５９」（以下、「引用文献」という。）には、
　「１．　まえがき」には、
　「現在、公開鍵暗号、なかでもＲＳＡ暗号が多大の注目を集め、実用化されているが、この暗号は、メッセージの暗号化、復号過程にべき乗演算及び剰余演算を繰り返し実行しなければならないため暗号化および復号の計算時間が膨大なものとなるという欠点を有している。
　本稿では法ｎを特別な形に設定した暗号を提案する。このように法ｎをある特別な形に設定した場合、安全性が若干犠牲になると考えられる。このため、本提案方式では従来方式と同様の安全性を確保するため、法ｎを十分大きくしている。以下ではＲＳＡ暗号の暗号化、復号時間の短縮方法について述べる。」（第１５４頁左欄第７〜１８行目），
　
　「２．１　ＲＳＡ暗号とその計算時間
　ＲＳＡ暗号は、原理の単純さ、高度の安全性といった優れた特長があるにも関わらず暗号化、復号を行う際に要求される計算量が過大なものになってしまうことが欠点とされている。この理由は暗号化、復号過程においてべき乗剰余演算を繰り返し実行しなければならないことによる。すなわち暗号化では、
　　　　　Ｍｅ≡Ｃ　ｍｏｄ　ｎ　　　　　　　　　　　（１）
復号では、
　　　　　Ｃｄ≡Ｍ　ｍｏｄ　ｎ　　　　　　　　　　　（２）
なる計算を繰り返し実行しなければならないことによる計算量の増加が問題となる。ただし、
　　　　　Ｍ：メッセージ
　　　　　Ｃ：暗号文
　　　　　ｅ：公開鍵
　　　　　ｄ：秘密鍵
　　　　　ｎ：ｐ・ｑ
　　　ｐ，ｑ：大きな素数（秘密）
である。なお一般にＲＳＡ暗号では２＜ｅ≪ｄと選ばれることが多いが、本稿では計算時間の短縮化について論ずるのでｅ及びｄにはこのような制約はないとして議論を進める。」（第１５４頁左欄第２０〜４１行目），
　
　「３．２　提案手法
　通常ｎはＲｘ−ｙの形で表される。ここで、このｙの桁数に制限を加えれば、法演算が除算を用いずに乗算と加算で置き換えることが可能であり、通常の除算で必要な除数の桁数に比例したステップ数の削減が可能になることが期待できる。以下、このことについて検討しよう。
　指数乗算法によりＭのべき乗を求める場合の第ｉステップにおける値をＣｉとする。第ｉステップにおいてｎを法とした自乗の演算を遂行する際、第　
ｉ＋１ステップにおける中間値Ｃｉ＋１はＣｉ２　ｍｏｄ　ｎ→Ｃｉ＋１として求まる。
　
　ここで、Ｃｉ２のＲｘ以上の部分をＣｉ（２）、
Ｒｘ未満の部分をＣｉ（１）とすると、
　
　　　　　Ｃｉ２＝Ｃｉ（２）・Ｒｘ＋Ｃｉ（１）　
　
　　　　　　　　≡Ｃｉ（２）・ｙ＋Ｃｉ（１）　　　　　　　　　（３）
　
となる。ここで乗算は並列処理により高速化を行うものとする。
次にＣｉ＋１２のＲ２ｘ以上の部分をＣｉ＋１（３）、
　
Ｒ２ｘ未満Ｒｘ以上の部分をＣｉ＋１（２）、
　
Ｒｘ未満の部分をＣｉ＋１（１）とすると、
　
Ｃｉ＋１２　
　
　＝Ｃｉ＋１（３）・Ｒ２ｘ＋Ｃｉ＋１（２）・Ｒｘ＋Ｃｉ＋１（１）　
　
　≡Ｃｉ＋１（３）・ｙ２＋Ｃｉ＋１（２）・ｙ＋Ｃｉ＋１（１）　
　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（４）
となる。そして式（４）の右辺がｎ桁以上の場合でもＣｉ２と同様、これをそのまま次のＣｉ＋２２の計算ステップで使用する。
　
　通常、・・・→Ｃｉ２→Ｃｉ＋１２→Ｃｉ＋２２→・・・のステップにお
　
いて桁数は各自乗計算ごとに増加するがＣｉ＋１（３）・ｙ２の桁数がＣｉ　
＋１（２）・ｙの桁数を越えないようにｙの桁数Ｙに制限を加えれば、最終のステップでの桁数をある値以下に制限することが可能になる。以下において、このことを検討しよう。
ここで
　　　　　　　　Ａ：ｎ　　　　　　　の桁数
　
　　　　　　　　Ｂ：Ｃｉ＋１（２）・ｙ　　の桁数
　
　　　　　　　　Ｃ：Ｃｉ＋１（３）・ｙ２　 の桁数
　
　　　　　　　　Ｄ：Ｃｉ＋１（３）　　　　の桁数
　
　　　　　　　　Ｙ：ｙ　　　　　　　の桁数
とすると、
　　　　　　　　Ｂ＝Ｙ＋Ａ　　　　　　　　　　　　　　（５）
　　　　　　　　Ｄ＝２・（Ｂ＋１）−２・Ａ　　　　　　（６）
　　　　　　　　Ｃ＝Ｄ＋２・Ｙ　　　　　　　　　　　　（７）
である。
　　　　　　　　Ｂ≧Ｃ　　　　　　　　　　　　　　　　（８）
なる条件より
　　　Ｙ＋Ａ≧２・（Ｙ＋Ａ＋１）−２・Ａ＋２・Ｙ　　　（９）
である。従って
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（１０）
として、最終ステップの桁数をＢ＋１以下に制限しうるｙの桁数の制限範囲が求まる。
　なお、ｙの値は式（１０）を満たす範囲でできる限り大であることが望ましい。さらに、数ステップに１回程度の法演算を許容すれば、式（１０）のｙの桁に関する制約条件をさらに大きくすることも可能である。」（第１５４頁右欄第２０行〜第１５５頁左欄下から第９行目，及び図１．），
　
　「３．３　高速演算の具体例
　ｙの桁数を上記の範囲に設定すれば、Ｃｉの桁数が高々Ｂ＋１桁以内におさまり、各ステップにおいてＣｉ２の演算結果が２（Ｂ＋１）桁以下に保たれることを具体例で示す。ここでは説明上１０進表現を採用することにする。通常のＲＳＡ暗号で行なう指数演算法（図３参照）による高速アルゴリズムに従って高速演算の手法を与える。ここでｋはｅを２進換算したときのビット数、ｅｉは同じくｅを２進換算したときの下位からのｉビット目の数値を表す。」（第１５５頁右欄第１〜１０行目，及び図３．），
　
　「５．２　Ｒｘ−ｙ回路の説明
　本提案方式をハードウェア構成した場合のブロック図を図９に示す。この回路は計算で取り扱うパラメータＭ，ｅ，ｙ，ｙ２を入れるためのレジスタと、Ｒ進乗算器Ｉ，ＩＩ，ＩＩＩと、Ｒ進加算器のみで構成する。この回路の乗算器ＩＩ，ＩＩＩは並列計算可能であり、依存する前段の処理としては乗算器Ｉの結果のみである。すなわち直列処理を必要とする部分はこの２つの部分のみである。よって、指数演算法の１ステップにあたるａ・ｂ　ｍｏｄ　ｎなる計算は、この２つの依存し合う直列処理部分に要するクロック数で計算可能になる。以上のように本提案方式は、ハードウェア構成をすれば、２クロックで演算可能である。」（第１５８頁左欄下から第５行〜同頁右欄第８行目，及び図９．），
　
　「６．まとめ」には、
　「又、公開鍵をいわゆる“電話帳”に１０進表現で掲載することを考えれば、図１０のように従来の方法では法ｎを全桁数字掲載する必要があり非常に長いものになるのに対し、本稿方式の共通鍵の場合には連続する９以外のランダムな部分の値のみ掲載すれば良いことになり、６０％程度のメモリーの節約になる。」（第１５９頁左欄第４〜９行目，図１０），
と記載されている。
　
３．本願発明１について
（１）対比
　本願発明１と上記引用文献に記載された発明とを対比すると、両者は共に、ＲＳＡ暗号方式の暗号化，復号化に関するものであり、しかも、本願発明１の「迅速計算方式」は、引用文献の図１の「Ｆａｓｔ　Ｃａｌｃｕｌａｔｉｏｎ　Ｓｙｓｔｅｍ」と同じであり、又、引用文献には、本願発明１と同
　
様に、Ｃｉ２　ｍｏｄ　Ｒｘ−ｙのｙの桁数に制限を加えれば、法演算が除
　
算を用いずに乗算と加算のみで行えること、及び、式（４）の右辺がｎ桁以
　
上の場合でもＣｉ２と同様、これをそのまま次のＣｉ＋２２の計算ステップ
　
で使用するので、通常、・・・→Ｃｉ２→Ｃｉ＋１２→Ｃｉ＋２２→・・・
　
のステップにおいて桁数は各自乗計算ごとに増加するがＣｉ＋１（３）・ｙ
　
２の桁数がＣｉ＋１（２）・ｙの桁数を越えないようにｙの桁数Ｙに制限を加えれば、最終のステップでの桁数をある値以下に制限することが可能になること、が記載されているので、
両者は共に、迅速計算方式で示されるＲＳＡ暗号方式の暗号化装置内のＭｅｍｏｄ　Ｒｘ−ｙ及び復号装置内のＣｄｍｏｄ　Ｒｘ−ｙの演算を実行する際に、通常の指数乗算法を使用して、該指数乗算法の第ｉステップのＣｉ２　ｍｏｄ　Ｒｘ−ｙのベキ乗剰余演算をｙにｙ＜Ｒｘ／２の制限を加え、指数演算法で使用される第ｉステップにおける値Ｃｉをｎを超える値のまま次のステップで使用するにもかかわらず、Ｃｉ値を或る桁数以下に制限することが可能となることによって、従来の除数の桁数に比例した処理時間を要する除算を使用することなく、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を実行することによって、上記のベキ乗剰余演算を高速処理すると同時に公開鍵をＲ進表現で公開する場合、連続するＲ−１以外のランダムな数字の部分、即ち、公開鍵の下位の数字部分のみを公開すればよく、ｘ／２桁以下の小さなサイズの公開鍵が使用可能となり、鍵管理メモリの節約及び該公開鍵が暗号化装置又は復号装置に手入力するという利便性を有する簡易な鍵管理を可能ならしめることを特徴とする高速ベキ乗剰余演算法を使用したＲＳＡ暗号方式を用いた暗号化装置及び復号装置である点では同じである。
　ただ、本願発明１においては、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を２回繰り返しを実行しており、又、高速ベキ乗剰余演算は「高速ベキ乗剰余回路（１）」で示される回路で構成されているのに対して、引用文献記載の発明においては、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を２回繰り返しを実行することは記載されておらず、又、高速ベキ乗剰余回路（１）についても記載されていない点で、両者は相違している。
　
（２）相違点についての当審の判断
　よって上記各相違点について検討すると、引用文献に記載の発明においても、演算式（３）で示される演算を複数回計算を行なうことは排除されておらず、又、本願明細書の発明の詳細な説明の欄には、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を２回繰り返し実行することの意味についての格別の記載はないので、引用文献記載の発明と比べて、本願発明１のように、Ｃｉ２≡Ｃｉ（２）．ｙ＋Ｃｉ（１）なる演算式で示される演算を２回繰り返し実行するところに格別の意味は認められず、該相違点は、格別の相違点であるものとは認められない。
　又、本願発明１の「高速ベキ乗剰余回路（１）」というのは、本願の図２と同じであるが、本願明細書の発明の詳細な説明の欄には、図２については、段落【０００４】及び【００１６】の記載によると（段落【００１６】における「〔図３〕」は、「〔図２〕」の誤記と認められる。）、式（１５）及び（１６）を実行する際、一般的に用いられる指数乗算法をハードウェア構成としたものであると記載されているので、本願発明１における「高速ベキ乗剰余回路（１）」というのは、本願発明１の文章で記載された部分を計算するための回路をブロック図で表現したものにすぎないものであって何等格別のものであるものとは認められず、指数乗算法を演算する回路構成を「高速ベキ乗剰余回路（１）」のように構成することは、引用文献に記載の発明から当業者が容易に発明をすることができた程度のことにすぎないものと認められる。
　
　従って、本願発明１は、上記引用文献に記載の発明から、当業者が容易に発明をすることができたものと認められる。
　
４．本願発明２について
（１）対比
　本願発明２と上記引用文献に記載された発明とを対比すると、両者は共に、ＲＳＡ暗号方式の暗号化，復号化に関するものであり、しかも、本願発明２の「迅速計算方式」は、引用文献の図１の「Ｆａｓｔ　Ｃａｌｃｕｌａｔｉｏｎ　Ｓｙｓｔｅｍ」と同じであり、又、引用文献には、本願発明２と同
　
様に、Ｃｉ２　ｍｏｄ　Ｒｘ−ｙのｙの桁数に制限を加えれば、法演算が除
　
算を用いずに乗算と加算のみで行え、その制限は、引用文献の式（１０）から明らかなように、同じ制限であり、又、式（４）の「ｉ＋１」を「ｉ」に置換すれば、本願発明２の演算式と同じになり、又、その右辺がｎ桁以上の場合でもＣｉ２と同様、これをそのまま次のＣｉ＋２２の計算ステップで使
　
用するので、通常、・・・→Ｃｉ２→Ｃｉ＋１２→Ｃｉ＋２２→・・・のス
　
テップにおいて桁数は各自乗計算ごとに増加するがＣｉ＋１（３）・ｙ２の
　
桁数がＣｉ＋１（２）・ｙの桁数を越えないようにｙの桁数Ｙに制限を加えれば、最終のステップでの桁数をある値以下に制限することが可能になること、更に、本願発明２の「高速ベキ乗剰余回路（２）」は、引用文献の図９の「Ｆａｓｔ　Ｃａｌｃｌａｔｉｏｎ」と同じであるので、
両者は共に、迅速計算方式で示されるＲＳＡ暗号方式の暗号化装置内のＭｅｍｏｄ　Ｒｘ−ｙ及び復号装置内のＣｄｍｏｄ　Ｒｘ−ｙなる演算を実行する際、通常の指数乗算法を使用して、該指数乗算処理の第ｉステップのＣｉ２　ｍｏｄ　Ｒｘ−ｙなるベキ乗剰余演算をｙの桁数Ｙについて、
整数を表す。）指数演算法で使用される第ｉステップにおける値Ｃｉをｎを超える値のまま次のステップで使用するにもかかわらず、Ｃｉ値を或る桁数以下に制限することが可能となることによって、従来の除数の桁数に比例した処理時間を要する除算を使用することなく、Ｃｉ２＝Ｃｉ（３）・ｙ２＋Ｃｉ（２）・ｙ＋Ｃｉ（１）なる形の演算式を実行することで、上記ベキ乗剰余演算を高速処理すると同時に公開鍵をＲ進表現で公開する場合、連続するＲ−１以外のランダムな数字の部分、即ち、公開鍵の下位の数字部分のみを公開すればよく、Ｙ桁以下の小さなサイズの公開鍵が使用可能となり、鍵管理メモリの節約及び該公開鍵が暗号化装置又は復号装置に手入力するという利便性を有する簡易な鍵管理を可能ならしめることを特徴とする下記「高速ベキ乗剰余回路（２）」で示される回路で構成されてなる高速ベキ乗剰余演算法を使用したＲＳＡ暗号方式を用いた暗号化装置及び復号装置である点では同じである（「高速ベキ乗剰余回路（２）」も同じである。）。
　ただ、本願発明２においては、Ｃｉ２＝Ｃｉ（３）・ｙ２＋Ｃｉ（２）・ｙ＋Ｃｉ（１）なる形の演算式を「１回」実行すること、と記載されているのに対して、引用文献記載の発明においては、式（４）として示されているところの、
Ｃｉ＋１２　
　
　＝Ｃｉ＋１（３）・Ｒ２ｘ＋Ｃｉ＋１（２）・Ｒｘ＋Ｃｉ＋１（１）　
　
　≡Ｃｉ＋１（３）・ｙ２＋Ｃｉ＋１（２）・ｙ＋Ｃｉ＋１（１）　
なる演算式で示される演算を何回実行するのか記載されていない点で、両者は相違している。
　
（２）相違点についての当審の判断
　よって上記各相違点について検討すると、引用文献に記載の発明においても、式（４）の演算を１回実行することは排除されておらず、又、本願明細書の発明の詳細な説明の欄には、Ｃｉ２＝Ｃｉ（３）・ｙ２＋Ｃｉ（２）・ｙ＋Ｃｉ（１）なる演算式を１回実行することの意味についての格別の記載はないので、引用文献記載の発明と比べて、本願発明２のように、Ｃｉ２＝Ｃｉ（３）・ｙ２＋Ｃｉ（２）・ｙ＋Ｃｉ（１）なる演算式で示される演算を１回実行したところに格別の意味は認められず、該相違点は、格別の相違点であるものとは認められない。
　
　従って、本願発明２は、上記引用文献に記載の発明から、当業者が容易に発明をすることができたものと認められる。
　
５．むすび
　以上のとおりであるので、本願発明１，２は、上記引用文献に記載の発明から当業者が容易に発明をすることができたものと認められる。したがって、本願発明は、特許法第２９条第２項の規定により特許を受けることができない。
　よって、結論のとおり審決する。