JPS61223876A - 暗号装置と累乗方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の技術分野］ この発明は、一般に暗号装置に関し、特に、機密保護さ
れていない通信チャンネルを介した伝送におけるデータ
の暗号化を可能にするために符号のない大きな値の整数
を計算する算術回路を備えた暗号装置に関する。

［発明の技術的背Ｉ！］ 暗号方式は、メツセージを特定の受信者以外には理解さ
れないことを目′的とするメツセージ伝送の技術である
。本質的に、通信の機密保護、確証およびディジタル信
号を確立すべき種々の通信装置内において、データの暗
号化には、このような方法が利用されている。

現代の通信システムにおいて、その通信速度と信頼性の
向上と共に、コストの低減が所望されている。多くの場
合、これらのシステムには、機密保護に関する一連の問
題がある。このようなシステムがいじくられることを妨
げ、伝送されるプライベート情報を保護するためには、
クレジット情報や機密保護情報などが暗号技術を用いて
伝送されることが必要である。この暗号技術を用いるこ
とによって、これらの情報は他の利用者にとって理解で
きないものとなる。

本質的に、暗号は計算の特殊な形式であって、このよう
なシステムは、その機密保護のための計算の困難性に基
づいている。これらのシステムは、非常に複雑な２つの
データの伝送を行なうので、暗号文の解読または暗号化
の反転処理を行なおうとする非認可のパーティ−には経
済的に手の届かないものとなる。一般に、メツセージを
暗号化するために使用される伝送には、アルゴリズムと
鍵とが含まれるのが典型的である。一方、１組の利用者
によって使用されている一般的な方法は公開されたもの
であっても良いが、いくつかのまたは全ての鍵情報は秘
密にされなければならない。メツセージ伝送の処理は、
暗号アルゴリズムをそのメツセージに適応する。この場
合、鍵は、暗号化を制御するための補助的な入力として
使用される。

従来の技術において広く使用されて来た多くの古典的な
暗号技術があるが、これらは、本質的に換字暗号から成
るものである。また、公開鍵暗号システムとして設計さ
れた暗号システムがある。

このようなシステムにおいては、復号鍵は、暗号鍵と異
なるものであって、暗号鍵から計算できるものではない
。利用者は、対の組合わせとなるこのような鍵を創作し
、その暗号鍵のコピーをその利用者の関係者に分配する
ことが可能である。しかし、復号鍵は秘密にしておく必
妄がある。この方式においては、関係者は、解読するこ
とができる創作者にだけデータを送ることができる。ま
たこの公開鍵暗号システムは、ディジタル署名を実現す
ることもできる。したがって、利用者は、プライベート
鍵を用いてメツセージを暗号化することによりそのメツ
セージに対する署名を行なうことができる。この場合、
他の誰かは署名の正当性を検査することができる。これ
は、雷名者の公開鍵を利用したメツセージへ復号を検査
することによってである。

暗号システムの主要な形式（Ｒ８Ａ　　暗号）は、数値
形式に符号化されるメツセージＢを暗号化する。この暗
号化は、例えば、そのメツセージ内の各文字毎に値を設
定し、そして、以下のような暗号文Ｃを得るために公開
鍵（ｅ、ｎ）を使用することによって実行する。

Ｃ＝Ｂ　　　。（モジュロＭ） すなわちＣは、Ｂ　をＭで割った時の余りである。ここ
で、全ての数値は、数百ビット長を有する大きな数であ
り、ｎは２つの大きな値の素数ｐとｑの積である。暗号
の！ｌ！密は、文字ｎからその因数であるｐとｑをくく
り出すことの実際的な不可能性に主に基づいている。復
号の動作は、以下のように指数が異なること以外は暗号
の動作と同様である。

Ｂ−Ｃ（モジュロＭ） Ｄは、ｐおよびｑに基づくものであるので、ｅ、および
ファクターＭであるＭからＤを計算することは非常に困
難である。Ｍのビット数に基づいて、その処理時間は極
端に変化する。例えば、Ｒ８Ａ方式の場合には、ワード
゛’　Ｉ　Ｔ　”は、Ａ＝０１゜Ｂ−０２，、、Ｚ−２
６と表わすことにより、以下のように暗号化することが
できる。数値０９２０は、ワード“ＩＴ”を示すもので
ある。ｎ　−２７７３−４７木５つ、およびｅ＝１７と
すると、暗号文は、Ｃ＝９２０”　　（モジュロ２７７
３）−９４８となる。ｐ−４７およびｑ−５９を使用し
て、ｄ−１５７を得ることができ、“ＩＴ”は９４８”
　　（モジュロ２７７３）＝９２０として計算すること
ができる。

モジュロ演算は、公開鍵暗号システム内で大きな部分を
占める。なぜなら、モジュロ演算がなめらかに連続して
変化し、連続する増加または減少関数として、不連続関
数に変化するためである。

複雑な大きな値の導入は、反転計算を極端に難しくする
。したがって、もしモジユラリティーが加えられるなら
ば、関数の値はでたらめに変化する。

モジュロ演算は、暗号機能によりすでに転送された情報
をさらに変化させるために、多くの暗号システムに使用
されている。したがって、モジユラリティーがこのよう
なシステムに加えられた時に、関数の値は完全に無秩序
となる。上記したようなデータの暗号化技術は比較的良
く知られているが、このような複雑な関数の実行に関係
する非常に困難な問題がある。これは、ビット長に関係
する使用される数が非常に大きなサイズであることに基
づいている。したがって、巨大な記憶容量と、暗号値を
計算するための極端に長い時間が必要となる。使用され
る数が大きくなれば、この種の関数を計算するために、
さらに多くの回路、さらに多くのスペースおよび時間が
必要となる。これは、ハードウェアおよびソフトウェア
−に厳しい制限を与える。したがって、このようなシス
テムの製造価格は、非常に高価ものとなる。このような
計算の複雑性に関する主なポイントは、以下の通りであ
る。暗号形式は、認可された送信者または受信者の仕事
よりも、その暗号解読の仕事がＮ（数の長さ）の増加を
伴って急速に増加する特性を有している。暗号の解読作
業がＮ１４　に比例すると仮定すると、暗号／復号作業
は、Ｎ３に比例する。

そして、Ｎが１０から２０へ２倍に増加した場合には、
認可された利用者の作業は８＠となるが、暗号を解読し
ようとする者の作業は、４０１０倍に増加する。伝送作
業への出資は、認可された利用者の場合には＄１０から
＄８０への増加であるが、暗号解読者の場合には合理的
な範囲の出資から多数の国の国家予算よりも多くの出資
へと増加する。

このようなシステムに関係する情報、および暗号のため
のＩＩ数の計算および実行の困難性は１文献゛°公開鍵
暗号方式の算術″マーチン・Ｅ・ヘルマン著、および“
°サイエンスフィック　アメリカン”１９７９年号、第
２４１巻、Ｎｏ２．１４６員から１５７頁に記載されて
いる。この文献は非常に情報が豊富であって、暗号装置
の発展の歴史およびこのようなシステムの特有の問題点
が詳細に示されている。またこの文献には、モジュロ演
算に関係する説明も詳細に記載されている。

【発明の目的〕

この発明の目的は、比較的短い時間で暗号計算を実行で
きるように必要な回路を最小限にして構成し、しかも認
可無しではその暗号の復号が非常に困難である暗号アル
ゴリズムを実行できる暗号装置を提供することである。

［発明の概要］ この発明の目的は、符号のない大きな値の整数Ｍをモジ
ュロ演算の基数としてメツセージデータである符号のな
い大きな値の整数（Ｂ）に符号のない大きな値の整数（
Ｅ）を累乗する暗号装置であって、上記各整数はＮビッ
トの大きさを有し、上記累乗の計算結果である符号のな
い大きな値の整数（Ｃ）は濃密保護されてない通信チャ
ンネルを介した伝送に適用される暗号装置において、上
記符号のない大きな値の整数Ｂに応答してこの整数を順
次２乗する第１の論理手段であって、上記順次２乗され
た整数を与えられた基数によって減少する手段を備え、
上記与えられた基数によって減少された上記２乗された
整数の′ｌｓ１の値を出力に供給する第１の論理手段と
、与えられた指数Ｅを示す第２の値を受信する入力およ
び上記第１の論理手段の出力に接続されたもう１つの入
力を有し、選択的に動作されるゲート手段と、上記ゲー
ト手段に接続された入力を有し、上記°ゲート手段によ
って制御されて動作する第２の論理手段であって、この
第２の論理手段に含まれている上記基数手段によりさら
に変形された上記第１の値の積を表わす出力値を出力し
、上記機密保護されてない通信チャンネルを介して伝送
される上記累乗の計算結果である符号のない大きな値の
整数（Ｃ）を上記出力に供給する第２の論理手段とを具
備する暗号装置によって達成される。

［発明の実施例］ 第１図は、この発明の特徴をさらに説明するために一般
的な暗号システムを示すものである。

通常の暗号システムにおいて、プライベートメツセージ
の伝送を所望するシステムは、アルゴリズムまたは一般
的な１１号化手順を有している。このメツセージは、メ
ツセージ元１０から伝送される。

このメツセージ元１０はコンピュータまたはモデム等の
ような複数の異なった装置から構成できることが最初に
理解されよう。メツセージデータは、ディジタルデータ
に変換された音声データ、またはメツセージ内容を示す
本質的に任意の種類のデータであることが可能である。

メツセージＰすなわち伝送されるべきデータは、“平文
”と呼ばれている。送信者は、この平文を暗号文Ｃにす
る端末すなわち回路モジュール１１を有している。この
暗号文Ｃは、電話回線、またはマイクロ波回線等のよう
な機密保護されてない通信チャンネルを介して伝送され
る。受信器１２は、暗号文Ｃを受信し、アルゴリズムす
なわち平文に変換するための復号手順に基づいてその暗
号文Ｃを処理する。通常の暗号システムにおいては、送
信者は、アルゴリズムすなわち一般的な暗号化手続きＧ
を有し、また　　　　　“鍵Ｋを得ている。この秘密を
守だめのこの鍵には、典型的には、多くのランダムな数
字の集合から成　　　　　−ることが可能な１組のパラ
メータである。このパラメータは、上記したアルゴリズ
ムを実行するために使用されるものである。

したがって、このアルゴリズムと鍵の両方によって、暗
号変換を特定する。この暗号変換は、平文Ｐを暗号文Ｃ
にするように動作する。受信者は、１１Ｋを知っている
ので、上記と反対の動作を行なうことにより、暗号文Ｃ
を平文に復号することができる。非認可利用者は通信チ
ャンネルにアクセスでき、しかも一般的な暗号手順およ
び暗号コードを知っても、鍵すなわちＫを知らないので
メツセージを解読することはできない。これが通常の暗
号システムである。

公開鍵暗号システムにおいては、鍵の配送のための機密
保護されたチャンネルは必要とされない。

このようなシステムにおいて、各受信者は、２つの別個
の鍵すなわち公開暗号手順を実行するための公開鍵およ
び公開復号手順を実行するための秘密鍵を生成する。こ
れらの鍵は反転変換を特定するのに使用されるという意
味において関係づけられているが、公ｎＩｉが与えられ
なければ秘＠鍵を得るための演算は実行不可能である。

これは、どんな大型のコンピュータでさえ、公開鍵から
秘密鍵への計算に千年あるいはそれ以上かかるというこ
とに由来している。したがって、この発明によるシステ
ムによって提供される機密保護は、暗号化のために美大
な数が使用されていることによるものである。

この美大な数の使用によって、利用されるべき回路に多
くの要求が課せられる。このため、その数学的関係は知
られているが、このような暗号処理を通常のコンピュー
タおよびハードウェアを用いて実行することは非常に困
■となる。したがって上記したように、この発明の主な
特徴は、符号長の長い整数あるいは数を使用し、しかも
データの暗号化を比較的短い時間で実行することができ
る効果的な回路構成の提供である。この装置によって実
行されるべき基本的な計算は、符号のない大きな値の整
数Ｍをモジュロ演算の基数として、符号のない大きな値
の整数Ｂに符号のない大きな値の整数Ｅ（指数）を累乗
するものである。これらの各整数は、Ｎピットの大きざ
を有することが可能である。各項は、複数のビットから
成る２進法、またはその他の形式で表現可能な数である
ことが理解されよう。

符号のない大きな値の整数である項“Ｂ″は、予め暗号
化すなわち符号化することが可能な平文データを示すも
のであって、上記したように、この°゛Ｂ″には、符号
のない大きな値の整数が累乗される。このアルゴリズム
の使用によって、非常に大きな数が提供され、この数の
各々はＮビットを有し、この発明による装置は、妥当な
実行時間内でこの計算を行なうことができる。このよう
な設計は、結果としてそのコストを最少にすることにな
る。符号のない大きな値の整数ＢのＥ乗（Ｂ木木Ｅ）の
計算は、Ｅ回の乗算を行なう必要がなく、本質的に２木
Ｎ−２回の乗算だけでよい。ここでＮは、Ｅのビット数
である。第１のステップにおいては、底数Ｂを次々に２
乗して、Ｂ木木２゜Ｂ木木４．Ｂ木木８．、、Ｂ木本（
２木木（Ｎ−１））までを得る。このステップでは、Ｎ
−１回の乗算が必要である。ここで使用した２重アスタ
リスク木本は累乗（例えば、ＢのＥ乗を８＊木Ｅとする
）を意味し、また単一のアスタリスク末は、乗算を意味
している。このようにして得られた２乗値の各々は、以
下に示すように、Ｅのビットにそれぞれ関連される。

ＢをＥのビット０に、Ｂ木木２をビット１に、Ｂ木木４
をビット２に、Ｂ木木８をビット３に、Ｂ木木１６をビ
ット４に、そしてＢ木本（２木木（ＮＭ））をビットＮ
−１に関係づける。Ｂ木本Ｅを計算するために、ビット
が１であるＥのビットに関連した２乗計算値が形成され
る。例えば、Ｅが２１（１０進数）すなわち１０１０１
　（２進数）である場合には、ビットＯ、ビット２およ
びビット４が１なので、次式が与えられる。

Ｂ木本Ｅ−Ｂ木木２１ −Ｂ木（Ｂ木木４）木（Ｂ＊木木１） この最後のステップでは、最大でＮ−１回の乗算が必要
とされる。したがって、全体の計算において必要な最大
の乗算回数は、 Ｎ−１＋Ｎ”ｌ−２木（Ｎ−２） となる。これまでの説明では、モジュロ演算にはふれて
おらず、モジュロ演算は余分の演算であるが、このモジ
ュロ演算により乗算されるべき数値が小さくなることに
よって、全体の仕事農は実際に減少される。後で説明す
るように、モジュロ演算は、全ての乗算が終了した後に
一度適用することができるものであるが、この発明のよ
る装置においては、その演算は頻繁に適用される。その
適用回数は、部分計算の実行回数に等しい。これは、モ
ジュロ演算の分散性によって実行可能となる。

整数ａおよびｂ、基数（モジュラス）Ｍ、および加算、
減算および乗算の演算因子（ｏｐ）間には、以下の様な
関係が成立つ。

（ａ　ｏｐ　ｂ）ｍｏｄ　Ｍ −（（ａ　ｎ１ｏｄ　　Ｍ）　ｏｐ（ｂ　ｍｏｄ　　Ｍ
）　）　ｍｏｄ　Ｍこの特性により、はぼ２Ｎビツトに
縮小された数に維持するために、乗算毎にモジュロ演算
を適用することができる。

さらに、各乗算は加算を順次実行することにより演算さ
れるので、乗算（各加算を伴っている）期間中に、モジ
ュロ演算を適用することができる。

この乗算では、はぼ２Ｎビツトに縮小された数に維持さ
れる。

第２図は、Ｂ木本Ｅを計算するための回路構成の一例を
示すものである。

平文データである区数Ｂは、Ｓレジスタとして表示され
ているレジスタ２０にロードされる。基数Ｍは、Ｍレジ
スタとして表示されているレジスタ２１にロードされる
。１は、Ｒすなわちリザルトレジスタとして表示されて
いるレジスタ２２にロードされる。Ｓレジスタの出力は
第１の乗算器２３に接続され、この乗算器２３の出力は
モジュロ回路２４に接続されている。そして、このモジ
ュロ回路２４の出力は、Ｓレジスタ２０の入力に帰還接
続されている。Ｓレジスタの出力は、選択的に動作する
ゲート回路２５にも接続されている。このゲート回路２
５は、指数Ｅのビット表示をその入力で受信する。

ゲーＩ・回路２５の出力は、第２の乗算器２６の一方の
入力に接続されている。この第２の乗算器２６のもう一
方の入力は、Ｒレジスタ２２の出力に接続されている。

乗算器２６の出力はモジュロ回路２７の入力に接続され
、このモジュロ回路２７の出力はＲレジスタ２２に直接
帰還接続されている。

後で説明されるように、乗算器およびモジュロ回路２３
．２４．２６．２７は、結合された回路から構成される
ものであるが、その動作を説明するために、第２図にお
いてはその構成を別々のモジュールとして示しである。

第２図から分るように、区数日はＳレジスタ２０に、基
数ＭはＭレジスタ２１に、そして１はＲレジスタ２２に
ロードされる。ゲート回路２５に供給される指数Ｅにつ
いては後で説明する。

１サイクルにおいて、Ｓレジスタ２０の値は、乗算器２
３により２乗され、モジュロ回路２４の基数Ｍによって
減少される。そして、この減少された値は、Ｓレジスタ
２０に戻される。したがって、１サイクル毎に、モジュ
ロ演算の基数をＭとした区数Ｂの２乗が順次増され、Ｓ
レジスタ２０に格納される。同時に、モジュロ演算の基
数をＭとした選択された２乗の積はＲレジスタ２２に送
られ、このＲレジスタ２２の内容は、結果的に、機密保
護されてない通信チャンネルを介した伝送にとって所望
の計算結果となる。各サイクルにおいて、指数Ｅの１つ
のビットは、選択ゲート回路２５へ移動される。

このビットの移動は、最小有効ビットから実行される。

したがって、その指数ビットが１の時には、乗算器２６
は、レジスタ２０および２２に記憶されている現在の値
ＳおよびＲの乗算を実行する。この乗算結果は、基数Ｍ
によって減少され、Ｒレジスタ２２に送られる。指数が
Ｏの時には、ゲート回路２５からの出力が１に等しくな
るか、またはＲレジスタ２２のクロック動作が上記した
乗算の実行を妨げる。

第３図は第２図に示した構成における動作のタイミング
を示す図であって、基数Ｍを無視した場合のＲ＝８木木
木本の計算が示されている。この図には、Ｓレジスタと
Ｒレジスタとの間のタイミング、並びに指数ビットの転
送が明確に示されている。上記したように、回路の大き
さの大幅な縮小は、乗算機能とモジュロ機能とを単一の
機能に結合することによって得ることができる。このこ
とを達成するためにまず最初に考えられることは、乗算
器がシフトおよび加算を順次実行できるようにることで
ある。これは、良く知られた技術であって、多くの通常
の乗算回路で利用されている。

第２に考えられることは、両者共にＮビットの符号長を
有する乗算されるべき数ＸおよびＹの双方を使用するこ
とである。Ｘ＝５　　（１０１）２進数、およびＹ＝６
　　（１１０）２進数とすると、ＸおよびＹは、以下に
示すように乗算される。ここで、木２はシフトを表わし
ている。また、線は、どのようにしてＸにまずＹの最大
有効ビット（ＭＳＢ）を乗じ、次にＹの中央のビット、
そして、Ｙの最小有効ビット（ＬＳＢ）を乗じるかを示
している。

−（１０１０＋１０１）木２十〇 −値１）木２ ＝１１１１０ ＝３０．（１０進数） シフトおよび加算を順次実行する乗算によって得られる
積をＰとすると、Ｘ　Ｇ、：　Ｙを乗じるアルゴリズム
は、以下のように与えられる。

１＝１ ｄｏ　ｗｈｉｌｅ　（ｉ≦Ｎ） Ｐ−Ｐ木２＋Ｘ＊Ｙ　（Ｎ−ｔ　＞ ｉ−ｉ＋　１ ｅｎｄｄ。

ここで、Ｙ（ｉ）はＹのｉ番目のビットを示している。

ＸとＹの乗算の代わりに、ＸをＸ／８、およびＹ　ｌ！
ｉ：Ｙ　＊　８　Ｇ：再ス’７−　ルＬ　ｒ、（Ｘ／８
）木（Ｙ木８）を計算する。もちろんこの結果は、Ｘ＊
Ｙの結果と変化はない。この再スケールの理由は、後に
説明するように、算術的オーバフローの防止を助けるた
めである。Ｙ　（−１）　−Ｙ　（−２＞　−Ｙ（−３
）＝Ｏとすると、アルゴリズムは以下のように与えられ
る。

Ｐ＝Ｏ ｉ＝１ ｄＯｗｈｉｌｅ（ｉ　　Ｓ；Ｎ＋３） Ｐ−Ｐ木２＋（Ｘ／８）　木Ｙ　（Ｎ−ｉ　）ｉ−ｉ＋
１ ｅｎｄｄ。

このｄｏ　ｗｈｉｌｅループのｍ後の３回のループは、
Ｙ木８を計算するためにＹを３回左へシフト（桁上げ）
させる。

したがって、モジュロ演算は、乗算演算と結合すること
ができる。Ａｏ　Ｗｋｉｌｃ　ループの各ループにおい
て、Ｐ＋Ｌ＊ＭがＰ　　ｍｏｄ　　ＭＩＣなルトイう条
件の下で、Ｐは、Ｐ　　ｍｏｄ　　Ｍの真値の近傍に維
持される。ここでＬは、−５≦Ｌ≦＋５のような整数で
ある。Ｐは、以下に示すような“集束剤″を適用するこ
とによってＰ　　ｍｏｄ　　Ｍ近傍に維持される。

１．１Ｆ　　Ｐ＜−２木木（Ｎ−１） ＴＨＥＮ　　ＭＭ＝３零Ｍ ２、ＩＦＰ≧２木木＜Ｎ−１） ＴＨＥＮ　　ＭＭ−−３木Ｍ ３、その他の場合は　　ＭＭ−Ｏ ｐ　　ｍｏｄ　　Ｍの近傍にＰを維持するために、Ｐ−
Ｐ十ＭＭとする。Ｍの倍数よりも±２木木（Ｎ−１）と
Ｐとを比較するほうが、その比較量は減少する。Ｐから
に＊Ｍを減算するというよりも、Ｐの最初の４ビツトだ
けがそれを調べるために必要とされる。

以下に示されているアルゴリズムの一例は、集束剤を用
いて変形したものである。

−Ｏ ｄｏ　ｗｈｉｌｅ　（ｉ　≦Ｎ＋３） ｉｆ（Ｐ＜−２木木（Ｎ−１）） ｔｈｅｎ　　Ｍ　Ｍ　−３木Ｍ ｉｆ（Ｐ≧２＊＊（Ｎ−１）） ｔｈｅｎ　　Ｍ　Ｍ　＝　−３木Ｍ Ｈ（−２木木（Ｎ−１）≦Ｐ Ｐ＜２木木（Ｎ−１＞　＞ ｔｈｅｎ　　Ｍ　Ｍ　＝　０ Ｐ＝Ｐ木２＋（Ｘ／８）木Ｙ（Ｎ−ｉ）＋ＭＭｉ＝ｉ＋
１ ｅｎｄｄ。

Ｐ　　ｍｏｄ　　Ｍの制限された範囲内にＰが集束剤に
より実際に維持されることを数学的に示すことは簡単で
ある。Ｘの再スケールは、この達成を助けている。集束
剤がＰの出力エクスカージョンをその入力エクスカージ
ョンよりも小さい０．２５Ｍに維持することは重要であ
る。Ｐを計算する算術のわずかな誤差によって、Ｐが−
２，５＜Ｐ〈２．５の範囲から離れて発散が開始される
ことはない。

ｄｏ　ｗｈｉｌｅループの終りにおいて、Ｐは−２，５
＜Ｐ＜２．５の範囲にある。簡単な゛クリンアップ”動
作は、Ｐを基数値の範囲すなわちＯ≦Ｐ〈Ｍに戻すこと
を必要とする。この゛°クリンアツプ″は、次のように
実行される。もしＰｔｆｉＯよりも大きい場合には、Ｐ
から３木Ｍを減算し、そして、Ｐが正数になるまでＭを
次々にＰに加算する。このときに、Ｐは所望の範囲に位
置するようになる。

結合された乗算およびモジュロ演算の一例は、次のよう
に与えられる。この例では、 ６木６　　ｍｏｄ　　５−３６　　ｍｏｄ　　５−１の
計算が示されている。

１．６末５　　ｍｏｄ　　５−１ ２、Ｘ−Ｘ木８＝４８　　Ｍ−Ｍ木８−４０これは、ア
ンダー７０−無しでＸ／８を承認するためである。

３、Ｙ−Ｙ木８−４８、Ｘ＊Ｙの代わりに（Ｘ／８）木
（Ｙ木８）を計算する。

４、Ｎ−Ｍのビット数＝６ ５、Ｘ／８＝６、Ｍ−４０，３木Ｍ＝１２０、■＝３２ ６、ｉ＝１、Ｙ（Ｎ−ｉ）−Ｌ　Ｐ＝Ｏ１２木Ｐ−０，
ＭＸ−６、ＭＭ＝Ｏ１ ２木Ｐ　十Ｍ　Ｘ　十Ｍ　Ｍ　＝　６ ７、ｉ−２、Ｙ（Ｎ−ｉ）−１、Ｐ＝６．２木Ｐ−１２
、ＭＸ＝６、ＭＭ−０， ２木Ｐ　＋　Ｍ　Ｘ　＋　Ｍ　Ｍ　−１８８、ｉ＝３、
Ｙ　（Ｎ−ｉ　＞　＝Ｏ１Ｐ＝１８．２木Ｐ−３６、Ｍ
Ｘ＝Ｏ１Ｍ　Ｍ　−０。

２木Ｐ十ＭＸ＋ＭＭ＝３６ ９＝−４、Ｙ　（Ｎ−ｉ　）　＝Ｏ１Ｐ＝３６．２木Ｐ
−７２、ＭＸ−０、ＭＭ−−，１２０１２木Ｐ＋ＭＸ＋
ＭＭ−−４２ １０、ｉ−５、Ｙ　（Ｎ−ｉ　）　−０゜Ｐ＝−４８，
２木Ｐ−−９６、ＭＸ＝０１ＭＭ−＋１２０．２木Ｐ＋
ＭＸ＋ＭＭ＝２４１１、　　＋−６、Ｙ　　（Ｎ−ｉ　
　）−０，Ｐ＝２４．２木Ｐ−４８、ＭＸ嵩０．ＭＭ−
０゜ ２木Ｐ＋ＭＸ＋ＭＭ−４８ １２、クリンアツプ： Ｐ−３木Ｍ−７２ １３、クリンアップ； Ｐ＋Ｍ−−３２ １４、タリンアップ Ｐ＋Ｍ−８ １５、クリンアップ Ｐ／８　＝　１　　値の修正 ここで、ライン２および３は、（Ｘ／８）木（Ｙ木８）
を計算するためのスケーリングを示すものである。ライ
ン５において、閾値Ｔは、スケーリングされたＭのため
に計算され、３２に等しい。ライン６乃至１１は、ａｏ
　ｗｋ’ｔｌ已ループの動作を示している。これらのラ
インにおいて、ＹＥＮ−ｒ　＞　−１テあれば、Ｍｘ＝
Ｘ／８であり、Ｙ（Ｎ−ｉ　）＝０であれば、ＭＸ＝０
である。ライン９において、Ｐは閾値を越えているので
、Ｍ　Ｍ−一３Ｍとなり、またライン１０においてＰは
閾値より小さいので、ＭＭ−＋３Ｍとなる。ライン１５
において、Ｐは最終的な正しい結果を得るために減少さ
れる。

第４図は、演算レジスタを介したデータバスを示すもの
であって、これらのレジスタは、互いに接続され、また
各加算器にも接続されている。第４図には２つの加算器
が示されている。このような加算器の構成は良く知られ
ているものである。

加算器３０の機能は、データのキャリーを加算すること
であり、一方加算器３１の機能は、マルチプレクサ３４
によって選択された値をＰ（積）レジスタ３３に加算す
ることである。この演算は、８ビツト“スライス″に分
割され、各サイクル期間中に、前のスライスからのキャ
リービットは、加算器３０によって、各Ｐスライスに加
算される。選択された値は、加算器３１によって、Ｐに
加算される。この結果として生じたキャリーピットは、
次のサイクルにおける次のスライスに入力されるように
フリップフロップにセーブされる。マルチプレクサ３２
は、加算器３０がＰまたは２木Ｐのいずれかを受信でき
るようにする入力を備えており、このマルチプレクサ３
２の出力は、加算器３０に接続されている。また、マル
チプレクサ３６は、加舜器３０がＣまたは２木Ｃのいず
れかを受信できるようにする入力を備えている。加算器
３０の出力は、加算器３１の一方の入力に接続されてい
る。この加算器３１の出力は、Ｐ（積）レジスタ３３に
接続されている。ＸＭマルチプレクサとして表示されて
いる付加的マルチプレクサ３４の入力には、Ｘ、Ｘ／８
．Ｍ、および＋３Ｍまたは一３Ｍとして表示されている
ＸＭレジスタが接続されている。このＸＭレジスタによ
って、加算器３１は、これらの任意のレジスタからデー
タを受信することができる。マルチプレクサ３４への３
−３　Ｍ　”入力は、レジスタ“３Ｍ″の反転出力であ
る。他の出力がどれも選択されないならば、マルチプレ
クサ３２または３４からＯの出力を得ることも可能であ
る。

第４図に示されているＣレジスタ３５の入力は加算器３
１の出力に接続されており、Ｃレジスタ３５の出力は、
マルチプレクサ３６を介して加算器３０の入力に接続さ
れている。ＰおよびＣレジスタ３３および３５は、Ｐ＋
Ｃまたはそのシフトされた形である２Ｐ＋２Ｇのような
結合された出力を有する結合レジスタと見なすことがで
きる。Ｃレジスタにキャリーが記憶されていることによ
り、一般に、演算期間中のどの時間における和も完全に
は計算されない。さらに言えば、この和は、ＰおよびＣ
レジスタ内のデータの和（Ｐ＋Ｃ）であり、シフトされ
た和は、これらのレジスタのシフトされた出力の和（２
Ｐ＋２Ｇ）である。その計算の終りで、ＣがＯになるま
で和Ｐ十Ｃに０が加算される。これは、キャリーレジス
タの″゛フラツシングパ呼ばれている。

これらの算術的なデータバスの結果として、以下のよう
な演算が可能となる。

Ｐ＋Ｃ＝Ｏ Ｐ＋Ｃ−Ｐ＋ＣＰ＋Ｃ＝２Ｐ＋２Ｃ Ｐ＋ＣＰ＋Ｃ −Ｐ＋Ｃ＋Ｘ／８　　　　＝２Ｐ＋２Ｃ＋Ｘ／８ｐ＋ｃ
　　　　　　　　　　　　　ｐ＋ｃ−Ｐ＋Ｃ＋Ｍ　　　
　　　　　　＝２Ｐ＋２０＋Ｍｐ＋ｃ　　　　　　　　
　　　　　　ｐ＋ｃ−Ｐ＋Ｃ−３Ｍ　　　　　　　−２
Ｐ＋２０−３Ｍｐ＋ｃ　　　　　　　　　　　　　ｐ＋
ｃ−Ｐ＋Ｃ＋３Ｍ　　　　　　　−２Ｐ＋２０＋３Ｍこ
のことから分るように、どのレジスタもＰレジスタ３３
からロードされることができる。さらに説明すれば、Ｐ
レジスタ３３はマイクロプロセッサによってａ−ドされ
、またこのマイクロプロセッサは、全ての回路を制御し
ている。したがって、マイクロプロセッサは、Ｐレジス
タ３３を介して、全てのレジスタをロードすることがで
きる。図に示されているように、Ｐレジスタ３３の出力
はマルチプレクサ３７および３８に接続されている。こ
れらのマルチプレクサ３７および３８は、ＳＹレジスタ
３９およびＲＹレジスタ４０にそれぞれ関連している。

ＳＹレジスタ３９およびＲＹレジスタ４０は、マルチプ
レクサ３７および３８に左回りでそれぞれ帰還接続され
、乗算Ｘ＊Ｙの実行を支援している。この場合、Ｙの最
大有効ビットは、シフトと加算とから成る乗算の各ステ
ップにおいて、Ｘ／８またはＯのどちらを加算するかを
選ぶために使用される。

第４図に示されているように、演算レジスタは、Ｐ１Ｃ
％Ｘ％ＲＹ、ＳＹ、Ｍおよび３Ｍとして表示されており
、以下に示すようなビット位置を有している。

Ｎ＋２Ｎ＋ｌ　　Ｎ　　Ｎ−Ｉ　　　Ｎ−２−・　　２
　　１　　０　　−１　　−２　　−３十−−−十−−
−十−−一十−−−十−−−−十−＋−−十〜−十−−
十−−−十−−−十−−−−一士Ｐ：　　Ｉ（−−−−
−−−−−−−−−−−−−−−−−−−−−〜−−−
−−−−−−−−−−−−−−）ＩＲＹ：　　　　　　
　　　　　　Ｉ（’″−−−−−−−　−−−−−−−
−−−−−−−−−−−−−一−−）ＪＳＹ：　　　　
　　　　　　　　　　Ｉ（−−−−−−−−−−−−−
−−−一−−−−−−−−−−−−−−＞ＬＸ：　　　
　　　　　　　　　　　Ｉ＜−−−−−−−−−−−−
−−−−−）ＩＭ：　　　　　　ｌ＜−−−−−−−−
−−−−一一一一一）１Ｍ３：　　　　Ｉ（−−−−−
−−−−−−−−−−−−−−ｍ−−−−−−−）Ｉ２
つのレジスタ３９および４０　（Ｓ　ＹおよびＲＹ）は
、計算Ｘ＊ＹのＹに対応している。ＳＹレジスタ３９は
、区数Ｂを順次２乗したものを記憶し、ＲＹレジスタ４
０は、最終的に結果Ｒとなる選択された２乗の積に対応
する。これらのレジスタ３９および４０は、第２図に示
したレジスタ２０および２２に類似している。Ｐレジス
タ３３は、部分積、およびモジュロ演算の基数をＭとし
てＸをＲＹ倍またはＳＹ倍した最終的な積を得るために
使用される。Ｍレジスタは、基数Ｍを保持し、３Ｍレジ
スタは、３木Ｍを保持している。

後で説明するように、指数Ｅは、マイクロプロセッサに
よって、種々の形式の指令シーケンスにおける１タイム
当りに１ビツトの割合いで回路に接続される。キャリー
セーブレジスタであるＣレジスタ３５は、後に説明され
るように、多くの部分に割込まれている。本質的に、Ｃ
レジスタ３５は、Ｐレジスタ３３の８つのビット位置毎
に２つのビット位置を有している。このため、どのサイ
クルの部分和も実際にＰおよびＣとなる。いくつかのレ
ジスタは、Ｎビットよりも多くのビットを有している。

例えば、Ｐレジスタ３３は、その上位桁の位置に３つの
余分なビットを有している。その理由は、部分和が、Ｐ
レジスタ３３が閾値Ｔ（−２木木（Ｎ−１））と比較さ
れる時間に−２，５木Ｍから２．５木Ｍまでの範囲の値
を有することが可能なためである。このことは、以下に
示されている。

Ｎ＋２Ｎ＋Ｉ　　Ｎ　　Ｎ−Ｉ　　Ｎ−２＠・・　　２
　　１　　０　　−１　　−２　　−３十−〜−十−−
−＋−−＋−−−−＋−−−−十−＋−−十−−＋−−
十−−−＋−−−＋−−−−＋Ｐ　：　　Ｉ＜−−−−
−−−−−−−−−−−−−−−−−−−−−−−−−
−−−−−−−−−−−−一＞Ｉ工１゛との比甲父　　
Ｉ ■　のためＶこ必多：　■ ■　とされる　　　１ ■　ビット　　　　　ｌ Ｐレジスタの値は示されているが、その他のレジスタの
値はどれも示されていない。Ｐレジスタ３３はその下位
位置に３つの余分なビットを有する。

なぜなら、８７′ＹがＰに時には加算されるからである
。ＳＹレジスタ３９およびＲＹレジスタ４０は、その下
位位置に３つの余分なピッ］・をそれぞれ有しており、
Ｎ＋３のシフトおよび加算サイクルにおいて、ＸとＹと
の積と同じ結果を得るためにＸ／８にＹ木８を乗算する
ことができる。そして、３Ｍレジスタは、後で説明する
ように、３木Ｍの値を保持するために、そのＯ位置に２
つの余分なビットを有している。この乗算は、゛タイム
スライス″されて実行される。これは、最初に、演算回
路が、レジスタの下位半分に対するシフトおよび加算機
能を実行するために使用され、そして次に、この同じ回
路が、レジスタの上位半分に対するシフトおよび加算機
能を実行するために再び使用されることを意味している
。

この゛タイムスライス″処理の結果、全てのデータを記
憶することは依然必要とされるが、計算回路の量はその
半分になる。この“タイムスライスパ処理によって、上
記各レジスタは、Ｎ／２ビット位置と＜Ｎ／２）−１ビ
ツト位置との間で、半分に分けられる。Ｐ、ＳＹ、およ
びＲＹレジスタ３３．３９．および４０には、下位半分
での演算を上位半分での演算に連結させるために使用さ
れるいくつかのリンキング（連結）ビットがある。

第５図は、この発明に係る暗号装置の構成を示すブロッ
ク図である。

本質的に、第５図の目的は、マイクロプロセッサ４０を
伴った暗号装置のインターフェースを示すことである。

このマイクロプロセッサ４０は、市場で販売されている
通常のマイクロプロセッサで良い。第２図に示した構成
を実行するためには、主要装置４１を備える必要がある
。この主要装置４１は、４２および４２Ｎとして表示さ
れている複数の従属装置と協同して動作するものである
。この従属ｉ置は、そのシステムの必要性に基づいて、
最低２つのユニットから４つのユニツ１−まで増やすこ
とができる。

第５図から分るように、第４図に示した演算レジスタか
らの種々の出力は、Ｘ／８．Ｐ、Ｃ，Ｙ等のように与え
られている。各装置に対して種々のクロック入力が存在
し、第１のクロックは１６ＭＨ２、第２のクロックは８
ＭＨｚで動作可能であり、また４ビツトのバスである制
御状態バスは、各装置の動作を制御するものである。マ
イクロプロセッサは、主要装置および従属装置への６つ
の制御入力を有しており、その４ビツトはアドレスビッ
ト、１ビツトはイネーブルビット、そして１ビツトは書
込みビットである。

第６図（第６ａ図および第６ｂ図）は、第５図に示した
主要装置４１を詳細に示す図である。

第６図を参照する前に、第５図かられかるように、マイ
クロプロセッサ４０は、簡単なメモリインターフェース
として主要装置および従属装置に接続されている。した
がって、マイクロプロセッサ４０には、双方向並列デー
タバス４３、並列アドレスバス４４．！込みイネーブル
制御４５．読出しすなわち出力イネーブル＆ＩＪＩＩＩ
４６およびチップイネーブル制御１１４７が設けられて
いる。これらは全て主要装置に接続され、また、アドレ
ス、書込みイネーブル、およびチップイネーブルは、従
属装置にも接続されている。

第６図に示されているように、マイクロプロセッサ４０
からの出力線は、１ｉｌＪ　Ｉ１１回路モジュール５０
にインターフェースしている。この制御回路モジュール
５０はＳＲレジスタ５１を備えており、このＳＲレジス
タ５１は、第５図に示したように主要装置と従属装置と
の間の制御状態バスに直接インターフェースしている。

制御回路５０には、ＬＲ／ＣＲレジスタとして表示され
ているレジスタ５２が接続されている。このレジスタ５
２は、磨込みアドレスに割当てられた指令（ＣＲ）およ
びロード（ＬＲ）レジスタを備えており、データのアン
ロードとビジー状態の読出しは、読出しアドレスに割当
てられている。

これらの機能は、主要装置のみによって実行される。マ
イクロプロセッサ４０によるチップイネーブル１４４の
付勢は、読出しまたは書込みイネーブル４５および４６
および１つのアドレスを伴って、データバス４３でのデ
ータ転送を引起こし、また、第５図に示した装置相間内
で実行されるべき関連動作を引起こす。

後で説明するように、上記装置相間内でのデータ転送を
可能にする８つの疑似書込みアドレスが存在するが、マ
イクロプロセッサ４０からのデータはこれには書込まれ
ない。したがって、この装置組には全部で１１のアドレ
スが存在する。主要装置は、演算回路の最小有効ビット
（左側のスライス）および最大有効ビット（右側のスラ
イス）の両方を有している。これらは、レジスタ５５お
よび５６に含まれている。各スライスは、第４図を参照
してすでに説明したレジスタおよび加算器を含んだ全て
のデータバスを有している。主要装置におけるビット数
は、最小有効スライスおよび最大有効スライスが便宜上
９ピツトおよび６ビ・ソトスライスから成り、他のスラ
イスは全て、８ビツトの符号長を有する。このことは、
レジスタ５５および５６を含んだ第６ｂ図から理解され
よう。最小有効スライスは、実際には、Ｘ／８の操作の
ための３つの付加的な最小有効ビットを伴った６ビツト
スライスである。最大有効スライスにおいて、Ｐレジス
タ（第４図で３３ンおよび加算器は、−２，５Ｍから２
．５Ｍの範囲で処理を行なうために３ビツトが余分に付
加されている。Ｐレジスタの下位１２ビツトは、ＮＲレ
ジスタ５７へのロードのために使用される。このＮＲレ
ジスタ５１は、サイクルカウントレジスタであり、その
出力は、ＮＣカウンタ５８に接続されている。このＮＣ
カウンタ５８は、１３ビツトのカウンタである。ＮＲレ
ジスタ５７は、自動乗算のためのサイクルカウントを記
憶するために使用される。このカウントされた値は、そ
の最大有効位置に付与された正符号（０）を伴って、Ｎ
Ｒレジスタ５７からＮＣカウンタ５８にロードされる。

そして、ＮＣカウンタ５８は、その符号が負になるまで
減少される。したがって、ＮＣカウンタ５８は、乗算処
理期間中に現われる部分積の数を制御し、これを制闇回
路５０に指示する。Ｐレジスタ３３の下位３ビツトは、
ＹＣ（Ｙ形状制御）レジスタ６０へのロードのために使
用される。このＹ形状制御レジスタ６０は、短い基数値
に対する“ループアラウンド″パス位置を決定する。Ｐ
レジスタ３３の符号ビットである最大有効ビットは、Ｐ
の符号を検査するために使用される。Ｐレジスタ３３の
上位４ビツトは、閾値比較器６１に供給され、そこでＰ
≧ＴおよびＰ＜−Ｔが調べられる。この閾値比較器６１
からの出力は、その比較結果を制御回路５０に直接知ら
せる。説明を簡単にするために、第１の制御回路をロー
ドおよびアンロード制御とみなすことにする。制御回路
５０がマイクロプロセッサ４０からのロード指令を受信
した時に、ロードレジスタ５２の最小有効位置に付与さ
れたロードフラグビットをクリアされる。これは、ＬＲ
レジスタ５２の左へのシフトを開始させる。ＬＲレジス
タからの最大有効ビットは、Ｐのための加算器の最小有
効ビットへ１またはＯのどちらかを入力するマルチプレ
クサゲート６１を制御するために使用、されている。そ
して、ＬＲレジスタ５２からのビットは、以下に示すよ
うに、Ｐレジスタ３３にシフト入力される。

Ｐ＋Ｃ−２Ｐ＋２Ｃ＋ＬＲｂｉｔ　　７ＬＲレジスタが
左にシフトされるので、１はロードフラグフリップフロ
ップ６３にシフト入力され、ロードフラグビットはＬＲ
レジスタにシフト入力される。ＬＲレジスタの全ての１
状態が検出器６４およびゲート６２によって検出された
時に、シフトは制御回路５０によってストップされる。

マイクロプロセッサは、ロードされるべき各８ビツトの
データに対してロード指令を繰返す。この場合、最大有
効ビットからロードが開始される。アンロードの制御は
、ロードの制御よりも単純である。制御回路５０がアン
ロード指令を受信した時に、制御回路５０ハ、ケート６
５オヨヒ６６（ｏＥ）ニヨリ、Ｎ−１からＮ−８ビツト
のデータバス４３への出力を許可する。マイクロプロセ
ッサは、Ｐレジスタを８ビツトを左へシフトし次の８ビ
ツトがアンロードできるようにするために、ロード指令
を出力しなければならない。

第６ａ図の右側にはタイミング回路が示されている。発
振器７０は、水晶発成により制御可能なものであり、第
１のクロック出力を出力する。この第１のクロック出力
は、従属装置へ送られる。第１のクロックは、フリップ
フロップ７１により２つのファクターに分割されて、最
小有効位置の演算のだめのＬＳおよび最大有効位置の演
算のためのＭＳとして表示されている２つのタイミング
制御信号が発生される。ＭＳは、第５図にも示されてい
る第２のクロックとして従属装置へ送られる。

図示されているように、フリップフロップ７１は、本質
的に、発振器７０によって供給されるクロック速度で切
換動作（トグル）するカウンタである。

フリップフロップ７１は、１１　Ｄ　１１形式のフリッ
プフロップであり、その出力ＱはＬＳとして表示されて
いる。このＬＳは、下位の“タイムスライス′。

演算を制御する。またＭＳとして表示されている出力こ
は、上位の゛タイムスライス°′演算を制御する。

ＣＲレジスタは、モジュール５２のＬＲレジスタと組合
わされているものであって、マイクロプロセッサ４０か
らの指令を受信するために使用されている。マイクロプ
ロセッサから見れば、ＣＲレジスタは、マイクロプロセ
ッサデータバス４３から非同期的にロードされる。主要
装置から見ると、書込みイネーブル信号がトリガするこ
とによって、内部クロックパルスに同期してＣＲレジス
タがロードされる。ＳＲレジスタ５１は状態レジスタで
あって、制御状態バスを介して、主要装置から従属装置
へ制御状態を送信するために使用されている。

ロードデータレジスタであるＬＲは、Ｐレジスタに１度
に１バイトのデータをロードするために使用されている
。そして、Ｐレジスタからのデータは、他のいずれかの
レジスタに転送される。ブロック５５および５６は、第
４図に示した演算論理における最小有効位置および最大
有効位置である。この算術論理の中間有効位置は、従属
装置に関係している。

上記したように、Ｙ形状レジスタ６０は、第４図に示し
たように、ブロック５５および５Ｇ内に含まれた実際の
データと同じ符号長で循環しているＹレジスタの切捨て
を制御するために使用されている。

その他のレジスタにおいては、左側にデータを整列させ
、右側にＯを詰込むことだけが必要とされる。

第７図は、第５図で４２および４２Ｎとして表示した従
属装置の一例を示すものである。第７図の上部は、従属
装置の制御回路を表わしており、マイクロプロセッサか
らの入力は、アドレス、チップイネーブル、書込みイネ
ーブル、および制御状態バスとして表示されている。第
７図の下部は、レジスタ８０内のスライス列を示してお
り、例えば第４図に示したような演算回路を具備してい
る。この演算回路は、従属装置が排他的に８ビツトスラ
イスから成る完全にレギュラーな装置であることを除い
て、主要装置で記載したものと同じである。

この従属装置は、レジスタの最小有効位置お・よび最大
有効位置のための主要装置と共に記載された特定の回路
を必要としない。本質的に、従属装置は、マイクロプロ
セッサ４０からの内部レジスタ転送指令、および主要装
置からの制御状態を承認することだけが必要である。従
属装置のタイミングは、ＬＳおよびＭＳ信号を再発生す
る単一のフリップフロップ８１で制御される。

第６図および第７図は、第５図のように接続された主要
装置および従属装置の機能的なブロック図を示すもので
ある。主要装置は、各制御サイクル期間中に、７つの制
御状態のうちの１つを発生させる。制御サイクルは、最
小有効゛タイムスライス′°のためのＬＳクロックサイ
クルと、最大有効゛タイムスライス°′のためのＭＳク
ロックサイクルとの２つのクロックサイクルに渡ってい
る。

これらの７つの制御状態を以下に示す。

（Ｐ十〇−Ｐ十Ｇ）　　　（アイドル／フラッシュ）（
Ｐ十Ｃ−２Ｐ＋２Ｃ）（ロード／アンロード）（Ｐ十〇
−０） （Ｐ＋Ｃ−Ｐ＋Ｃ＋Ｍ） （Ｐ＋Ｃ−Ｐ＋Ｃ−Ｍ３） （Ｐ＋Ｃ−Ｐ＋Ｃ＋Ｍ３） （Ｐ＋Ｃ−２Ｐ＋２Ｃ＋ＹＸ、５ｈＮｘｔ）これらの制
御状態のうちの第１の制御状態は、ディフォルトまたは
アイドル動作であり、Ｐレジスタにキャリーをフラッシ
ュする。１２の制御状態において、主要装置における動
作は実際に次のようになる。

Ｐ十Ｃ−２Ｐ＋２Ｃ＋ＬＲ７゜ ＬＲ−２木ＬＲ＋ＬｏａｄＦ　ｌ　ａａ。

ＬｏａｄＦ　　Ｉ　　ａｏ−１ これは、ａ−ドおよびアンロード動作を行なうものであ
る。

最後の制御状態において、“十Ｙ　Ｘ　”は、ＹＥＮＤ
ビット（選択されたＹレジスタの最大有効ビット）が１
の時はいつでも各装置がＸ／８を加算することを意味し
ている。“Ｓ　ｈ　Ｎ　ｘ　ｔ　”は、選択されたＹレ
ジスタが次のサイクル期間中にシフトされることを示し
ている。すなわち、この部分の演算は１サイクル遅延さ
れる。制御状態は、指令レジスタＯＲの内容によって決
定される。

第４図に戻ると、ＳＹレジスタ３９およびＲＹレジスタ
４０はロードおよびシフ１−されて、他のレジスタの“
タイムスライス″構造を利用できることが示されている
。これによって、必要とされるロードおよびシフト動作
を支援するために必要なマルチプレクサとビンの数は減
少される。

簡単な方法は、選択されたＹレジスタを１クロックパル
ス当り１ビット位置左へ単に回転させることであり、レ
ジスタの内容が ＡＢＣＤａｂｃｄ であった場合には、 ８ＣＤａｂｃｄＡ となる。

この方法は、ロードするためのＰレジスタの対応するビ
ットまたはシフトするためのＹレジスタの次のビットを
選択するために、Ｙレジスタの各フリップフロップ当り
２ウエイのマルチプレクサを必要とする。

゛°タイムスライスパされた構造を伴った並列ロードを
促進するために、Ｙレジスタの最大有効（ｍｓ）である
半分と最小有効（ＩＳ）である半分は、Ｐレジスタの構
成に基づいてスタックされる。シフトされる前の状態は
、 ＢＣＤ ｂｃｄ であり、シフト後の状態は、 ＣＤａ ＣｄＡ となる。しかし、そのシフトの関係はそのまま同じに維
持される。２つの側の接続は各チップ境界線で必要とさ
れ、２つの接続は左端と右端とを接続するためにも必要
であることが明らかとなる。

同じ結果を達成するために、Ｙレジスタを２つのステッ
プにおいて下方へ回転することかできる。

これは、ざらに緊密にＰレジスタの動作に対応し、マル
チプレクサおよびサイド接続の必要が無くなる。この場
合のロードは、２クロツクサイクルで実行される。その
開始状態は、 Ｐ：　　ＡＢＣＤ ａｂｃｄ ｙ：　　ｘｘｘｘ ×　×　×　× である。ここで、ビット記号１１　Ｘ　ＩＩは、未知の
データまたは任意のデータを表わしている。１クロツク
サイクル後においては、次のような関係が成立つ。

ｐ：　　ａｂｃｄ ＡＢＣＤ Ｙ：　　　ａｂｃｄ ｘｘｘｘ そして、２クロツクサイクル後では、 Ｐ：　　ＡＢＣＤ ａｂｃｄ Ｙ：　　ＡＢＣＤ ａｂｃｄ となる。Ｐレジスタが垂直方向に回転されるので、それ
は、Ｙに垂直にシフトされる。

Ｙの回転が２ステツプで実行されることも可能である。

Ｙレジスタが垂直方向に２ステツプで回転されると、そ
の最終的な結果は、前に示した１ステツプでの水平方向
の回転と同じになる。これには、付加的なフリップフロ
ップが必要となる。その開始状態において、ｘ＋１は、
その開始される値がいずれの値でも良いことを示してい
る。

ＡＢＣＤ ａｂｃｄ 第１のクロックパルスにおいて、全てのビットは下方ヘ
シフトされ、各段の底部からのビットは、次の段の上部
および左へ移動される。この場合に、最も左の前段の上
部は、最も右の段の上部に移動される。

ｂｃｄＡ ＡＢＣＤ 補助的なフリップ７０ツブは、捕獲されたビット１１　
ａＩＩを有しており、このビットは別の方法で消去され
る。第２のクロックパルスにおいて、補助的なフリップ
フロップのビットが最も右の段の上部に移動されること
以外は、第１のクロックパルスでのシフトと同じシフト
が行われる。

ＢＣＤａ ｃｄＡ 補助的なフリップフロップを無視すれば、この結果は、
１ステツプでの水平方向回転と同じになるが、１つのサ
イドでの接続は各装置の境界線で必要とされる。また、
回転動作とロード動作とを比較することによって、フリ
ップフロップの底部の段への入力は、両方の動作と同じ
であることが明らかである。これらの制御は、Ｙレジス
タの回転またはロードのいずれかに基づいている。マル
チプレクサは、この配置における左端のビットが右端へ
移動されるべきであるかどうかを選択するために必要と
される。この場合の制御は、クロックサイクルが２クロ
ツクサイクルの最初の半分に関係しているか、または後
の半分に関係しているかに基づいている。

この設計は、ＳＹレジスタにおいて、そのレジスタの右
端への入力が必要でないことを除いて、ＲＹレジスタお
よびＳＹレジスタの両方において使用することができる
。これら２つのレジスタは絶対に何時にシフトされない
ので、同じサイドの接続は、両方のＹレジスタにサーブ
することができる。このようにして、マルチプレクサは
、出力ビンに付加される。この出力ビンは、第６図およ
び第７図のＹ　　ｓｅｌラッチ８０に示したように、現
在使用しているＹレジスタを選択する。入力ビンは、両
方のレジスタに接続され、付勢されてないレジスタによ
って無視される。余分のマルチプレクサにかかる費用は
、サイド接続よりも非常に少なくなる。

、前に示したように、乗算の形式（Ｘ／８）木（８木Ｙ
）を実行するために、Ｙ値の晟小有効（ＩＳ）端に３つ
のＯを加えることは好都合である。これは、サイクルカ
ウンタの最後の３つの状態を解読して、Ｏ値を強制する
（Ｙのシフトを不可能にする）か、または３つの余分な
Ｏを実際にＹレジスタへ入れるかによって行われる。こ
の余分なビットは、底（ＩＳ）列の右端に加えられなけ
ればならない、また垂直方向へのシフト形式が元の状態
を維持するために、上側の列の右端にも同じ数のピッが
加えられる。第１のクロックパルスにおいて、ビットは
左端から最も右（ＦｒＬい）の段の上部へシフトされる
が、第２のクロックパルスで、左端からのビットは、前
に示した段（元の最も右の段）と同じ段に移動される。

基数ｍ（および底敷ｂ）のビット長が装置組の算術演算
サイズよりも小さい時には、演算を実行するためにいく
つかの調整が必要である。まず、装置組内のデータを左
端に合せるために、ｍおよびｂｌの後に０をロードする
。データをロードするための時間は、縮められないが、
小さな計数値がロードされて、各乗算サイクルの時間が
減少される。Ｐ、Ｘ、ＳＹ、ＲＹ、Ｍおよび第３の値は
、その右端に同じ数の余分なＯをすべて有することにな
る。この演算は前の演算と同じであるが、加算器の最も
右端はいつもＯを加算および減算している。減算の補数
および加算キャリー法は、Ｏの加算とは異なったＯの減
算のための付勢を生成する。しかしその結果は、どちら
の場合においても正しい。

しかしながら、ＲＹレジスタの回転は、打のられなけれ
ばならない。このＲＹレジスタの打切りの必要性は、２
つの設計の選択から生じるものである。第１の選択は、
１つのＹレジスタを共用しＰレジスタとしては別個のも
のを使用するというよりはむしろ、Ｐレジスタが２乗お
よび結果の累算の両方に分けられ、別のＹレジスタが２
乗および結果のために使用されることである。この選択
は、マルチプレクサの数を減少させることができる。第
２の選択は、仮想の次の結果を計算し、そしてその指数
がＯビットである場合にはそれを除去することによって
、実行ＲｆＪをデータと独立して保つものである。これ
らの選択は共に、ＲＹレジスタの内容が、シフトされた
時に予めサーブされることを必要としている。Ｎ＋３の
シフト後、全てのビットが元に位置に戻るので、回転は
データを予めサーブする。

ＲＹレジスタは、最も右の位！のような所望される演算
位置にマルチプレクサを付加することによって、種々の
長さの符号長に打切られることができる。もし、マルチ
プレクサが、第１（ＩＳンのクロック周期期間中に、通
常の次のビットの代わりに左端のビットをこのような位
置に挿入するならば、この回転はその位置で打切られる
。

第８ｂ図乃至第８ｅ図は、Ｎ−８の時のレジスタの調整
の４つの場合を示すものである。ここで、第８ｂ図の符
号長は９、第８Ｃ図の符号長は８、第８ｄ図の符号長は
６（Ｎの半分よりも大きい）に打切られ、第８ｅ図の符
号長は２（Ｎの半分よりも小さい）で打切られている。

第８ａ図は、特別なマルチプレクサを示すものであって
、簡単のために多くのマルチプレクサを省略したもので
ある。第８ｂ図乃至第８ｅｌｉ４における左側の表は、
シフトされる前のレジスタの状態、および第１および第
２のクロックパルス後におけるレジスタの状態を示して
いる。また、右側のブロック図は、１ステップ当りのデ
ータフローに等しい。

制御データ（Ｓ［ｎｌビット〉は、Ｙ形状レジスタに設
定され、これは、各装置につきほんの少しのビットだけ
を必要とし、ＰレジスタからすなわちＰレジスタの最も
右側の部分から各８置にロードされることができる。

第９図は、第５図に示したブロック図と類似するもので
あるが、第９図には、マイクロプロセッサ４０にインタ
ーフェースするような演算回路および制御回路がそれぞ
れ設けられた主要装置および従属装置のブロック図が示
されている。このブＯツク図の目的は、この配置の概念
を明らかにすることである。上記したように、暗号化を
実行する全体の処理回路は、１つの主要装置８０および
４つの従属装置８６乃至８６Ｎから成る。この装置の制
御は、標準的な８ビツトマイクロプロセツサであるマイ
クロプロセッサ４０によって行われる。主要装置８５は
、第４図に示したような演算回路、および第６図に示し
たような制御回路から成る。同様に、各従属装置８６乃
至８６Ｎは、主要装置内の演算回路と同一の演算回路、
および従属制御回路から成る。

主要装置および従属装置は、その設計が類似している。

第６図に５０として示したような制御回路は、マイクロ
プロセッサ４０からの指令を通訳するシーケンス制御装
置である。また、従属装置における制御機能は、制御回
路５０およびマイクロプロセッサ４０から従属装！！８
６乃至８６Ｎの演算回路へ制御信号を犀に送るだけであ
る。第９図の“演算回路”は、第６図に示したブロック
５５および５６、および第７図に示したブロック８０に
対応している。

第１０図は、第４図に示した回路と同様の演算回路のブ
ロック図を示すものであって、この図では、第４図に示
した種々のモジュールがどのようにして主要装置および
従属制御ユニット９０のような関連する制御回路にイン
ターフェースしているかが直接示されている。

上記したように、この発明の主な目的は、整数の累乗演
算を実行し、その際にこの演算と基数関数とを組合、わ
せで実行するようにして演算回路を減少させることであ
る。本質的に、累乗の演算は、連続する乗算およびモジ
ュロ演算組に分けられ、ざらにこの連続する乗算および
モジュロ演算組は、連続するシフトおよび加算演算に分
けられる。さらに、回路の複雑性の減少を達成するため
に、゛°タイムスライス”技術が利用されている。第１
０図に示した回路は、上記したように時分割されたもの
である。

第１１図は、第１０図の演算回路内で論理的遅延の最も
長いバスだけが示されている演算回路を示すものであっ
て、これは、最も患い伝搬遅延を示すものであり、この
伝搬遅延はクロックサイクルよりも短くなければならな
い。各乗算／′モジュロ演算は、約Ｎ回の加算およびシ
フトサイクルから成り、各加算およびシフトサイクルは
、４クロツクサイクルに分割されている。最も悪い場合
の伝搬遅延バスは、タイミング制御フリップ７０ツブ９
１からＸマルチプレクサ９２、入出力回路９３．９４、
ＸＭマルチプレクサ９５および加算器９６の９つのリッ
プルキャリーレベルを介して、設定時間を有するキャリ
ーセーブフリップフロップ９７へのバスである。これは
、伝送速度がキャリーセーブスライス（８ビツトとして
示されている）の幅および接続間遅延に主に基づいてい
る。

第１２図は、“タイムスライス°′されたレジスタ（Ｓ
ＹレジスタまたはＲＹレジスタ）のその典型的な部分を
示す論理的なブロック図である。第１２図では、レジス
タ中に記憶された２つのビット（１ビツト幅）だけが示
されているが、この設計は、所望の符号長の算術演算を
実行するために、Ｎビットまで繰返えされる。この設計
は、第４図および第８図に示したようなＲＹレジスタお
よびＳＹレジスタを構成するために利用される。Ｎピッ
ト長の演算においては、第１２図に示されているＮ／２
の部分が実行される。なぜなら、各部分が記憶された２
つのビットを有しているからである。この演算は、最小
有効部および最大有効部に分割されて、任意の部分１１
　Ｍ　１１において、ＭおよびＭ＋Ｎ／２が記憶される
。

ＳＹおよびＲＹレジスタは、１０個の論理ゲートとそれ
ぞれ等価であり、この１０ｍの論理ゲートは、各フリッ
プフロップに４つ、そしてマルチプレクサに２つである
。第１２図から分るように、第４図に３７および３８と
して示したマルチプレクサは、２つの″゛Ｄ゛′Ｄ゛′
フリツプフロツプ１０００１を制御する。この２つの７
リツプフロツプ１００および１０１は、必要とされるビ
ットを記憶するものである。

第１３図は、第４図に示したような“タイムスライス′
°されたＸＭレジスタおよびＸＭマルチプレクサの構成
を示すものである。前に示したように、×（成敗）、Ｍ
（基数）およびこれらの値は、どの演算期間中にも一定
の値を維持する。これらの値は、時間クリティカルなも
のではないので、“Ｄ　１１フリツプフロツプの代わり
にローゲートカウントラッチ回路が使用される。したが
って、モジュール１１０および１１１は、それぞれラッ
チ回路である。

第１３図は、簡単のためにデータフローパスだけを示す
ものである。Ｐレジスタからの値は、計鐸の開始時にＸ
Ｍおよび３Ｍレジスタにロードされる。前述のＸ／８お
よび３Ｍは、乗算／モジュロ演算の集束を行なうために
必要とされる。

第１４図は、第４図に３０．３１．３３および３５とし
て示されている８ビツトキヤリーセーブスライスの加算
器およびＰおよびＣレジスタを示すブロック図である。

この回路は、半加算器および全加算器の両方を使用して
いる。この図では、半加算器をＨｌおよび全加算器をＦ
として示しである。データフローは、下方および左方に
進む。

乗算およびモジュロ機能は、１サイクル内でインターリ
ーブされる。したがって、１サイクル当り２回の加算が
実行される。この図に示された回路においては、キャリ
ーピットの゛フラッシングは、Ｎ／８回の加算を必要と
し、また加算器への入力は、ＰおよびＣレジスタ入力以
外は全てＯである。１サイクル当り２回の加算が実行さ
れるので、キャリーをフラッシュするため、すなわちＰ
レジスタへの全てのキャリービットを合計するために、
Ｎ／１６サイクルが必要とされる。

第１４図の下方には、全加算器Ｆと半加算器Ｈとの間の
実際の入力を示したブロック図が示されており、この図
から分るように、全加算器Ｆからの出力は、半加算器の
入力に接続されている。半加算器Ｈには２つの出力があ
り、その一方は次の半加算器に直接接続され、他の一方
は、全加算器の入力に接続されている。全加算器も同様
に２つの入力端子を有している。第１４図に関連して示
したこの小さなブロック図の目的は、隣接した加算器間
のキャリー接続を示すことにより、第１４図の接続関係
を明白にすることである。

上記した動作は、当業者の知識範囲内のものであり、シ
ステム構築に基づいて、当業者は上記したような構成の
暗号装置を実施できよう。とにかく、上記したようなシ
ステムは、マイクロプロセッサ４０によってその動作が
制御される。以下の記載は、符号のない大きな値の整数
をモジュロ演算の基数として符号のない大きな値の整数
に符号のない大きな値の整数を累乗する演算を実行する
ために、マイクロプロセッサ４０から主要装置および従
属モジュールへ送られる指令を説明するものである。

Ａ、転送指令 二Ｍ＋Ｐ 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＰレジスタからＭ（基数）レジスタをロー
ドする。

：　　Ｍ３−Ｐ 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＰレジスタからＭ３（３木基数）レジスタ
をロードする。

ム：＝Ｐ 呼出し方ニアドレスＴ８Ｄに疑似的に書込む。

指令の説明：ＰレジスタからＮＲ（サイクル力／　　　
　　ラント）レジスタをロードする。

：　　ＹＣ−Ｐ 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＹＲ回転機能の打切りをセットするために
ＹＣ（Ｙ形状）レジスタ をロードする。

：　　　　　　＝ 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＰレジスタからＹレジスタをロードする。

ＲＹまたはＳＹレジ スタのいずれかは、予め選択され なければならない。

−：　　　−Ｐ　　５Ｙ＝Ｐ　　５ｅｌ−ＲＹ）呼出し
方；アドレスＴＢＤに疑似的に書込む。

指令の説明：ＰレジスタからＸレジスタをロードする。

次に、Ｐレジスタか らＳＹレジスタをロードする。

最後に、ＲＹレジスタを選択する。

Δ：Ｙ＝ｓｅｌ−Ｙ 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＰレジスタからＲＹレジスタをロードする
。次に、ＳＹレジスタ を選択する。

ム：５ｅｌ− 呼出し方ニアドレスＴＢＤに疑似的に書込む。

指令の説明：ＳＹレジスタを選択する。

Ｂ、演算指令 ：　（Ｐ＋Ｃ＝０ 呼出し方：ＣＲレジスタのアドレスＴＢＤにＴＢＤを書
込む。

指令の説明：ＰおよびＣレジスタをクリアする。

直重ニー（２１二上」ｕＬ二ＮＣシ」しＬ反旦上二］）
呼出し方：ＣＲレジスタのアドレスＴＢＤにＴＢＤを書
込む。

指令の説明：サイクルカウントレジスタ（ＮＲ）からサ
イクルカウンタ（ＮＣ）を ロードすることによって、乗算を 開始する。

ＮＲにはＮ＋２の値がロードされ、この指令は、カウン
タＮＣを２木（Ｎ＋５）にセットする。ＮＣが負でない
時はいつでも、ＮＣは、カウントダウンして２木（Ｎ＋
３）サイクルをカウントして停止する。この２つの因子
は、各制御周期が最小有効タイムスライスのための１ク
ロツクサイクルおよび最大有効タイムスライスのための
１クロツクサイクルを含んでいることから必要とされる
。

また、この制御周期は２つずつ配置されている。

すなわち、ＮＧのビット１がＯの場合にＸの乗数が選択
され、ＮＣのビット１が１の場合にＭの乗数が選択され
る。

乗算が実行された時、その乗算器のビジーフラグはクリ
アされる。この乗算の結果は、次のようになろう。

Ｐ＋Ｃ−（Ｘ＊Ｙ　　ｍｏｄ　　Ｍ） ここでＫは、−３≦に≦２である。

マイクロプロセッサは、Ｎ木４／１６だけ待機し、全て
のキャリーをＰにフラッシュさせるためにクロック周期
をセットする。この時の結果は次の通りである。

Ｐ＝（Ｘ＊Ｙ　　ｍｏｄ　　Ｍ）＋に＊Ｍ次に、マイク
ロプロセッサは、Ｐを０≦Ｐ＜Ｍの範囲内に収めるため
に、Ｐレジスタを°“クリンアップ″する。

Ｃ，クリンアップ指令 Δ：Ｐ〉０ならばＰ＋Ｃ−Ｐ＋Ｃ−Ｍ３呼出し方：ＣＲ
レジスタのアドレスＴＢＤにＴＢＤを書込む。

指令の説明：Ｐレジスタが正であれば、３木Ｍを減算す
る。この指令は、積を °“クリンアップ″シて、 ＰをＯ≦Ｐ＜Ｍの範囲に収めるた めに必要とされる。

ム：Ｐ〈０ならばＰ＋Ｃ＝Ｐ＋Ｃ十 呼出し方：ＣＲレジスタのアドレスＴＢＤにＴＢＤを書
込む。

指令の説明：Ｐｌ、；ジスタが負であればＭを加算する
。この指令は、積を “クリンアップ”して、Ｐを ０＜Ｐ＜Ｍの範囲に収める。

ム：　　十　冨　＋　＋ 呼出し方：ＣＲレジスタのアドレスＴＢＤにＴＢＤを書
込む。

指令の説明：ＰレジスタにＭレジスタを加算する。

この指令は、３木Ｍを計算するた めに使用される。

Ｄ、入出力指令 ：（ロー゛） 呼出し方ニアドレスＴＢＤにバイトを書込む。

指令の説明二マイクロプロセッサからＬＲレジスタに８
ビツトを入力する。

Ｐレジスタ８ビットを左にシフト し、ＬＲレジスタからＰレジスタ の最小有効位置における８ビツト （上位８ピツｌ〜）をロードする。

ｂＡ：　アンロー°） 呼出し方ニアドレスＴＢＤからバイトを読出す。

指令の説明：Ｐレジスタからマイクロプロセッサへ８つ
の最大有効ビットを出力 する。

ム：　ビジー 呼出し方ニアドレスＴＢＤからバイトを読出す。

指令の説明：乗算器がビジー状態であることを示すごジ
−フラグを読出す。

上記したようなマイクロプロセッサ指令を利用して、基
本的なアルゴリズム演算を実行する方法の一例を以下に
示す。

以下のマイクロプロセッサのアルゴリズムにおいて、変
数を次のように定める。

ｂ−区数 ｅ−指数 ｍ−基数 １ｍ−基数および区数の符号長 １ｅ−指数の符号長 ＩＣ−デバイスセットの符号長 これらの変数は最初に与えられるものであって、符号長
はビット数を意味している。また混乱を避けるために、
マイクロプロセッサの変数には小文字、デバイスセット
のレジスタには大文字を使用する。

アルゴリズムは、計算の各ステップ毎に疑似コードの書
式で示されている。マイクロプログラム指令は、上記し
たようなデバイスセットに使用されている。これらの指
令は、常にカッコ内に、例えば（ロード）のように示さ
れている。

まず、基数ｍは、以下の疑似コードに示すように、その
最大有効ビットを最初にしてＰレジスタにロードされる
。この場合、基数ｍがバイト列として記憶されるものと
仮定している。また、ビジー状態時の待機が乗算指令の
後でのみ必要とされると仮定している。

（Ｐ＋Ｃ−０） ｆｏｒ　ｉ　＝　１ｍ／８−１　　ｄｏｗｎ　ｔｏ　　
Ｑ　　ｔｏ　ｂｅｇｉｎ（ｌｏａｄ）　ｍ　［ｉ　］ ｎｄ ＰおよびＣを最初にクリアすることは、Ｐレジスタの左
側および右側部の余分なビットをクリアすることを確実
にする。一般に、ｍをＰレジスタの左端に合せるために
、その布部に０をロードすることがある。この場合、全
ての符号長は８の倍数である。次に示すアルゴリズムは
、必要とされるＯのロードを示すものである。

ｆｏｒ　ｉ　−１ｔｏ　　（ｌ　ｃ　−１ｍ）／８　ｄ
ｏ　ｂｅｇｉｎ（ｌｏａｄ）Ｏ ｎｄ そして、ＰレジスタからＭレジスタへｍを転送し、そこ
で３木Ｍを計算して、この３木ＭをレジスタＭ３にロー
ドする。− （Ｍ−Ｐ） （Ｐ十〇＝Ｃ＋Ｍ） （Ｐ＋Ｃ−Ｐ＋Ｃ＋Ｍ） （Ｍ３＝Ｐ） 値ｌｍ＝２をＮＲ（サイクンルーカウント）レジスタに
ロードする。これは、その計算の符号長が前の計算にお
ける符号長と異なっている場合、またはこの計算が電源
投入後最初に実行されるものである場合にのみ必要とさ
れる。この値がｎｒ［１］およびｎｒ［ｏ］と名付けら
れた２バイトであるとすると、以下に示されるように、
この値は、その最大有効バイトを最初にしてロードされ
る。

（Ｐ＋Ｃ−０） （ｌｏａｄ）　ｎ　ｒ　［１］ （ｌｏａｄ）　ｎ　ｒ　［０］ （ＮＲ−Ｐ） 符号長１ｍは、ＲＹレジスタの切捨て（トランケーショ
ン）を必要とすることも可能である。この切捨て符号長
（トランケーションレングス）は、ＹＣ（Ｙ形状）レジ
スタによって設定される。このＹＣレジスタは、各装置
のバイトよりも少ないバイトから成っているが、そのデ
ータはＰレジスタを介してロードされるので、そのデー
タは、ダミー（０）バイトによって分割される。Ｙ形状
データがｙｃｄと名付けられたバイト列内に格納（装胃
当り１バイト）されると想定し、またＳフィルのダミー
バイトが従属装置（Ｒ大有効従属装置を除く）毎に必要
とされ、ｍフィルのダミーバイトがマスター装置に必要
とされるとすると、Ｙ形状データは次の手順でロードさ
れる。

（Ｐ＋Ｃ＝Ｏ） ｆｏｒ　ｉ　＝４　　ｄｏｗｎ　ｔｏ　２　　ｔｏ　ｂ
ｅｇｉｎ（ｌｏａｄ）　ｙｃｃｉ　［ｉ　］ ｆｏｒｊ＝１　　ｔｏ　　ｓフィル　ｄｏ　ｂｅｉｎｇ
（ｌｏａｄ）Ｏ ｎｄ （ｌｏａｄ）　ｙｃｄ　［１］ ｒｏｒｊ＝１ｔｏ　　ｍフィル　ｄｏ　ｂｅｇｉｎ（ｌ
ｏａｄ）Ｏ ｎｄ （ｌｏａｄ）　ｙｃｄ　［０］ （ＹＣ＝Ｐ） 偶数値の指数を許可するために、ＲＹレジスタに１をセ
ットする。偶数値の指数においては、この手順の７ラグ
メントは必要ない。

（Ｐ＋Ｃ−０） （ｌｏａｃｌ）１ （ＲＹ＝Ｐ、　　ｓｅ　　Ｉ　　　ＳＹ）ｍのロードと
同様な形式で、置数すをレジスタＰ、ＸおよびＳＹにロ
ードする。

（Ｐ＋Ｃ−０） ｆｏｒ　ｉ　−１ｍ／８　−１　　ｄｏｗｎ　ｔｏ　　
Ｏｄｏ　ｂｅｇｉｎ（１ｏａｄ）　ｂ　［Ｉコ ｎｄ ｆｏｒ　ｉ　−１ｔｏ　　（Ｉｃ−１ｍ）／８　ｄｏｂ
ｅａｉｎ（１ｏａｄ）　Ｏ ｎｄ （Ｘ−Ｐ、５Ｙ−Ｐ、ｓｅｔ　　ＲＹ＞これは、Ｏ−デ
ィングフェーズを終了する。この回路は、主要な計算を
実行できる状態に現在なっている。この主要計算を実行
するためにその時間の大部分が使用される。

指数ビットをカウントするために１１０の指数ビットを
カウントするためにｊｌおよびプログラムループのｆｔ
繰返しのポーズをカウントするためにｋを使用する。こ
のポーズによって、セーブされたキャリーをＰレジスタ
にフラッシュする時間が１ｑられる。最小フラッシュ時
間は、乗１１ＩＦＩ＃間の１／１６である。乗算レジス
タに何も（キャリーは除く）加えられない時にフラッシ
ュが自然に発生するので、特定のフラッシュ指令は必要
ない。

以下に示すぎぎコードにおいて、指数の最小有効ビット
を検査するための“Ｉ　ｓ　ｂ　”と名付けられた機能
、およびその指数を１ビツト右ヘシフトするための’ｓ
　ｈ　ｒ”と名付けられた機能が使用されている。

ｊ場１ｅ／４ ｆｏｒ　ｉ　＝　ｉ　　ｔｏ　　Ｉ　ｅ　　ｄｏ　ｂｅ
ｇｉｎまず、Ｐレジスタは、置数の１乗すなわちｂの１
乗を保持する。これは、指数のビットＯに関連したもの
である。もし指数が基数であれば、たとえＲＹが１に等
しい場合でも、ＲＹ−８をセットする。このループの他
の繰返しでは、ＲＹ＠ＲＹの前の値に最後の２乗をした
値にセットする。

１ｆｌｓｂ−１ ｔｈｅｎ　ｂｅｇｉｎ　　（ＲＹ−Ｐ、　ｓｅ　ｌ　　
ＳＹ＞ｎｄ ｅｌｓｅ　　ｂｅｇｉｎ　　　（ｓｅ　　ｌ　　　ＳＹ
）ｎｄ ｓｈｒ（ｅ） “°１ｔ″状態に関係なく、次にいつも８ｍレジスタが
選択されることに注意されたい。ＳＹをＸ四乗じること
により、次の２乗を計算する。ＰおよびＣレジスタをク
リアし、基本的な乗算サイクルを開始する。そして、そ
の基本的な乗算が完了するをを持って、モジュロ演算を
゛クリーンナツプ”する。このクリ°−ンアップ操作の
各ステップにおいて、キャリーがＰレジスタにフラッシ
ュされるのを待機しなければならないこと注意されたい
。

（Ｐ＋Ｃ−０） （スタート乗算：ＮＣ−ＮＲ）　　・・・２乗を計算す
るための乗算 （ビジー）期間中は何も 実行しない　　　　　　　　・・・乗算が完了するのを
待つ （Ｐ２ＯならばＰ＋Ｃ−Ｐ＋Ｃ−Ｍ） ｒｏｒＫ−ｔｔｏｆｔ ｄｏ　ｎｏｔｈｉｎｇ　　　　　−・・キャリーをフラ
ッシュする （　Ｐ〈０ならばＰ＋Ｃ＝Ｐ＋Ｃ＋Ｍ）ｆｏｒ　ｋ＝１
　　ｔｏ　ｆｔ ｄｏ　ｎｏ℃旧ｎｇ　　　　　　・・・キャリーをフラ
ッシュする （　　ＰｒｏならばＰ十Ｃ−Ｐ＋Ｃ＋Ｍ）ｒｏｒ　ｋ−
１ｔｏ　ｆｔ ｄｏ　ｎｏｔｈｉｎｇ　　　　　　−・・キャリーをフ
ラッシュする （　　Ｐ＜ＯならばＰ十Ｃ−Ｐ＋Ｃ＋Ｍ）ｆｏｒ　ｋ−
１ｔｏ　ｆ　ｔ ｄｏ　ｎｏｔｈｉｎ（１ （Ｘ−Ｐ、５Ｙ−Ｐ。

ｓｅｌ　　ＲＹ）　　−ＸおよびＲＹ へ２乗をロード する 次のＲ値のための乗算は、この計算を時々スキップ可能
であること以外はこれと同様である。計算が終了した時
、Ｐレジスタの結果はそのままの状態にされる。ＲＹレ
ジスタへのこの結果の転送は、ループの最初に実行され
る。

ｉｆ　　Ｉ　ｓｂ　（ｅ）　−０℃ｈｅｎｊ＝ｊ−１ｉ
ｆ　　ｌ５ｂ（ｅ）≧１　　ｏｒ　Ｊ　＜Ｏｔｈｅｎ　
ｂｅｇｉｎ（Ｐ＋Ｃ−０） （スタート乗算：ＮＣ＋ＮＲ）・・・２乗を計算するた
めに乗算 を実行する （ビジー）期間中は何も 実行しない　　　　　　　　　・・・乗算が完了するの
を持つ （Ｐ≧ＯならばＰ＋Ｃ−Ｐ＋Ｃ−Ｍ３）ｆｏｒ　Ｋ−１
ｔｏ　ｆｔ ｄｏ　ｎｏｔｈｉｎ（１”・キャリーをフラッシュする （　Ｐく０ならばＰ＋Ｃ−Ｐ十Ｃ＋Ｍ）ｆｏｒ　ｋ＝１
　　ｔｏ　ｆｔ ｄｏ　ｎｏｔ旧ｎｇ　　　　　　・・・キャリーをフラ
ッシュする （　　Ｐ＜ＯならばＰ＋Ｃ−Ｐ十Ｃ＋Ｍ）ｆｏｒ　　ｋ
＝１　　ｔｏ　　ｆ　　ｔｄｏ　ｎｏｔｈｉｎｏ　　　
　　　”’キャリーをフラッシュする （　Ｐく０ならばＰ＋Ｃ−Ｐ＋Ｃ＋Ｍ）ｆｏｒ　ｋ＝１
　　ｔｏ　ｆｔ ｄｏ　ｎｏｔｈｉｎｇ　　　　　　・・・キャリーをフ
ラッシュする ｎｄ ｎｄ これでメインループが終了する。検査させる最後の指数
ビットがいつも１であるのので、その結果は常にＰレジ
スタにあり、この結果をアンロードする。このダミーロ
ード指令は、次のアンロードのために、Ｐレジスタを左
へ８ビツトシフトさせる。

ｒ［Ｏ］＝（アンロード） ｆｏｒ　１−１ｍ／８　−１　　ｄｏｗｎｔｏ　　Ｏｄ
ｏ　ｂｅｇｉｎ　　（ｏ−ド）・・・ダミーロード ｒ［Ｎ＝（アンロード） ｎｄ デバイスセットの左のデータを消去するために、以下の
ような手順が加えられる。

（Ｐ＋Ｃ−０）　　　　　・・・Ｐをクリアする（Ｘ−
Ｐ、５Ｙ＝Ｐ、ｓｅｔ　　ＲＹ）・・・ＸおよびＲＹを クリアする （ＲＹ−Ｐ、ｓｅ　Ｉ　　ＳＹ） ・・・ＲＹをクリアする （Ｍ−Ｐ）　　　　　　　・・・Ｍをクリアする以上の
説明から、ここに示した装置は、極端に長い符号長を含
んだ複雑な算術計算を実行することが可能であり、しか
もその計算速度は高速化され、また回路の複雑性が緩和
されることが理解されよう。したがって、上記した構成
の装置は、リザル１−（Ｒ）および２乗（Ｓ）累算のた
めに共通の加算器を使用している。この加算器は、基数
（Ｍ）および乗数（Ｘ）の両方の乗算を加ｉするために
も必要とされる。積累算レジスタ（Ｐ）は、分配され、
別々のレジスタ状態における結果および２乗ファクター
（ＲＹおよびＳＹ）が供給される。このことにより、マ
ルチプレクサの数は減少される。基本的な論理回路は、
゛タイムスライス”されており、これによって、２つの
ファクターの組合わせ論理が減少される。、基数の３倍
は、主要制御Ｉロジックの動作を緩和させるアルゴリズ
ムを支援するために予め計算されている。このシステム
は、全てのデータをロードするためのシフトおよび加算
キャリー能力を利用している。このため、多くの場合に
、ラッチが、高価なフリップフロップよりも多く使用さ
れている。

論理回路は区分されているので、全ての不均等な論理回
路は主要装置に配謬され、従属装置は、均一な回路を有
することになる。標準的な形式のマイクロプロセッサは
、簡単な相互接続されたシステムおよび簡単なプログラ
ム設計によって、主要装置および従属装置の制御を行な
うことができる。したがって、この発明による装置は、
廉価でしかもシステム要求に対する高速応答が可能とな
り、最少限の費用で信頼できる暗号化技術の利用を提供
することができる。

上記したような整数、および種々のレジスタのピットサ
イズは、単なる一例であって、他の算術計算に適応する
ためにこの値を変化することが可能であることが理解さ
れよう。同様に、特許請求の範囲に示されたこの発明の
技術的範囲内でこの装置を変形することが可能である。

【図面の簡単な説明】

第１図は通信チャンネル内で使用される暗号装置を示す
ブロック図、第２図はこの発明による暗号化のアルゴリ
ズムを計算する構成を示すブロック図、第３図は指数Ｅ
が２１である場合における第２図に示した構成のサイク
ル毎の演算シーケンスを示すタイミング図、第４図はこ
の発明の一実施例に係る暗号装置に使用される算術デー
タバスを示すブロック図、第５図はこの発明によるマイ
クロプロセッサ制御下での暗号装置を示すブロック図、
第６ａ図および第６ｂ図はこの発明に使用される主要装
置の実施例を詳細に示すブロック図、第７図はこの発明
による従属装置を示すブロック図、第８ａ図乃至第８ｅ
図は大きさが異なった基数を処理する構成を示すブロッ
ク図、第９図は第５図に示した構成と類似したこの発明
による暗号装置システムを示すブロック図、第１０図は
制御回路に接続された第４図の構成を示すブロック図、
第１１図は第４図に示したような算術回路における伝送
遅延を決定するために使用されるブロック図、第１２図
はこの発明に使用されるレジスタステージのために必要
とされる回路を示すブロック図、第１３図はこの発明に
使用されるレジスタおよびマルチプレクサの構成を示す
ブロック図、第１４図はこの発明に使用される加算器お
よび累算器の構成を示すブロック図である。 １０・・・メツセージ元、１１・・・回路モジュール、
１２・・・受信器、４０・・・マイクロブ巳セッサ、４
１・・・主要装置、４２〜４２Ｎ・・・従属装置。 出願人代理人　弁理士　鈴　江　武　彦×四＝ロ　ＣＯ
Ｅ Ｎ−２＝６ ＝２

Claims (20)

【特許請求の範囲】
1. （１）符号のない大きな値の整数Ｍをモジユロ演算の基
   数としてメツセージデータである符号のない大きな値の
   整数（Ｂ）に符号のない大きな値の整数（Ｅ）を累乗す
   る暗号装置であつて、上記各整数はＮビツトの大きさを
   有し、上記累乗の計算結果である符号のない大きな値の
   整数（Ｃ）は機密保護されてない通信チヤンネルを介し
   た伝送に適用される暗号装置において、 上記符号のない大きな値の整数（Ｂ）に応答してこの整
   数を順次２乗する第１の論理手段であつて、上記順次２
   乗された整数を与えられた基数によつて減少する手段を
   備え、上記与えられた基数によつて減少された上記２乗
   された整数の第１の値を出力に供給する第１の論理手段
   と、 与えられた指数Ｅを示す第２の値を受信する入力および
   上記第１の論理手段の出力に接続されたもう１つの入力
   を有し、選択的に動作されるゲート手段と、 上記ゲート手段に接続された入力を有し、上記ゲート手
   段によつて制御されて動作する第２の論理手段であつて
   、この第２の論理手段に含まれている上記基数手段によ
   りさらに変形された上記第１の値の積を表わす出力値を
   出力し、上記機密保護されてない通信チヤンネルを介し
   て伝送される上記累乗の計算結果である符号のない大き
   な値の整数（Ｃ）を上記出力に供給する第２の論理手段
   とを具備する暗号装置。
2. （２）上記第１の論理手段は第１のレジスタを具備し、
   この第１のレジスタは、符号のない大きな値の整数（Ｂ
   ）を受信する入力と、上記整数を順次２乗し、上記与え
   られた基数によつて上記２乗された整数を減少させる第
   １のモジユロ乗算手段に接続された出力とを有し、上記
   モジユロ乗算手段の出力は、上記第１の値を上記第１の
   レジスタに記憶するために、上記第１のレジスタの入力
   に接続されている特許請求の範囲第１項記載の暗号装置
   。
3. （３）上記第２の論理手段は第２のレジスタを具備し、
   この第２のレジスタは、第１の２進値を受信する入力と
   、第２のモジユロ乗算手段の入力に接続された出力とを
   有し、上記第２のモジユロ乗算手段のもう一方の入力は
   、上記選択的に動作されるゲート手段に接続され、上記
   第２のモジユロ乗算手段の出力は、上記第２のレジスタ
   が上記符号のない大きな値の整数（Ｍ）を記憶できるよ
   うに、上記第２のレジスタの入力に接続されている特許
   請求の範囲第１項記載の暗号装置。
4. （４）上記第２のレジスタに入力される上記２進入力は
   ２進値１である特許請求の範囲第３項記載の暗号装置。
5. （５）上記与えられた基数を表わす値を記憶するように
   構成された基数レジスタを具備し、この基数レジスタは
   、上記与えられた基数をこの基数レジスタへ供給する上
   記第１および第２の論理手段に接続された出力を有して
   いる特許請求の範囲第１項記載の暗号装置。
6. （６）上記第１の論理手段は、第１の複数のレジスタを
   有する算術回路と、上記複数のレジスタの任意の１つの
   出力を選択するマルチプレクサ手段と、加算手段とを具
   備し、上記第１の複数のレジスタの１つは上記基数の値
   を記憶し、もう１つは与えられたファクターが乗算され
   た上記基数を記憶し、さらにもう１つは上記符号のない
   大きな値の整数（Ｂ）を記憶し、上記マルチプレクサ手
   段は上記複数のレジスタに接続され、上記加算手段は上
   記マルチプレクサ手段に接続された入力と、変形された
   第１の値を示す別の連続する値を上記加算器手段の出力
   に供給するために上記第１の値に対応する第２の入力と
   を具備している特許請求の範囲第１項記載の暗号装置。
7. （７）符号のない大きな値の整数Ｍをモジユロ演算の基
   数としてメツセージデータである符号のない大きな値の
   整数（Ｂ）に符号のない大きな値の整数（Ｅ）を累乗す
   る暗号装置であつて、上記各整数はＮビツトの大きさを
   有し、上記累乗の計算結果である符号のない大きな値の
   整数（Ｃ）は機密保護されてない通信チヤンネルを介し
   た伝送に適用される暗号装置において、 複数の入力および複数の出力を有し、上記符号のない大
   きな値の整数（Ｂ）および与えられた基数を記憶する複
   数の入力装置を備えた算術計算手段と、１つの与えられ
   た入力装置を選択するために上記入力装置に接続されて
   いる手段と、上記選択された装置に入力装置に記憶され
   た情報に上記符号のない大きな値の整数を乗算する乗算
   手段と、上記与えられた基数により減少された上記符号
   のない大きな値の数値の連続する２乗の記憶を実行する
   ための最小および最大有効ビツトに従つて上記乗算され
   た情報を記憶するレジスタ手段と、指令データを発生す
   る手段とを備えている主要論理手段と、 上記主要論理手段の上記出力に接続された複数の入力を
   有し、乗算された情報である上記記憶された情報に従つ
   て上記主要論理手段からの選択されたデータを受信する
   従属回路手段であつて、上記主要論理手段によつて発生
   された上記指令データに従つて上記乗算された情報を順
   次処理する算術計算手段を備えている従属回路手段と、 上記主要論理手段の入力端子に接続され、処理されるべ
   きメツセージデータおよびこのメツセージデータに割当
   てられている与えられた基数を示す一連の命令を上記主
   要論理手段へ供給するマイクロプロセツサとを具備して
   いる暗号装置。
8. （８）上記主要論理手段は上記算術計算手段の動作を制
   御するクロツク発生手段を備え、上記従属回路手段のた
   のタイミング波形を選択された出力に供給する特許請求
   の範囲第７項記載の暗号装置。
9. （９）上記主要論理手段および上記従属回路手段の双方
   の上記計算手段は第１および第２の選択可能なレジスタ
   を備え、上記第１のレジスタは上記与えられた基数によ
   つて減少された上記符号のない大きな値の整数（Ｂ）の
   ２乗された値を記憶し、上記第２のレジスタは上記与え
   られた基数によつてさらに変形された上記第１のレジス
   タ内に記憶された上記値の積である出力値を記憶する特
   許請求の範囲第７項記載の暗号装置。
10. （１０）上記主要論理手段は、この主要論理手段の計算
    状態を上記従属回路手段に示すために、この従属回路手
    段に接続された出力を有している状態レジスタを具備し
    ている特許請求の範囲第７項記載の暗号装置。
11. （１１）上記主要論理手段と上記従属回路手段の双方は
    、上記乗算の結果である部分積を記憶する部分積レジス
    タを備えている特許請求の範囲第７項記載の暗号装置。
12. （１２）上記乗算手段は第１および第２の加算器を具備
    し、上記第１の加算器はキヤリーを加算し、上記第２の
    加算器は値を上記部分積レジスタに加算する特許請求の
    範囲第１１項記載の暗号装置。
13. （１３）上記主要論理手段は、上記マイクロプロセツサ
    からの指令信号を受信するように構成された制御回路と
    、上記指令に応答して、上記算術計算手段の動作を制御
    するためのシフト動作を開始するロードレジスタとを具
    備している特許請求の範囲第７項記載の暗号装置。
14. （１４）上記主要論理手段は、乗算の演算期間中に累算
    された積の回数を制御するために、上記乗算手段によつ
    て実行された乗算の回数を示すカウントを記憶するよう
    に動作するサイクルカウントレジスタを具備している特
    許請求の範囲第７項記載の暗号装置。
15. （１５）上記主要論理手段は、上記マイクロプロセツサ
    からの指令をデータバスを介して受信する制御レジスタ
    を具備している特許請求の範囲第７項記載の暗号装置。
16. （１６）符号のない大きな値の整数Ｍをモジユロ演算の
    基数としてメツセージデータである符号のない大きな値
    の整数（Ｂ）に符号のない大きな値の整数（Ｅ）を累乗
    する暗号装置であつて、上記各整数はＮビツトの大きさ
    を有し、上記累乗の計算結果である符号のない大きな値
    の整数（Ｃ）は機密保護されてない通信チヤンネルを介
    した伝送に適用される暗号装置において、 メツセージデータである上記符号のない大きな値の整数
    （Ｂ）を受信する入力を有し、上記符号のない大きな値
    の整数を出力に供給する第１の手段と、 与えられた基数（Ｍ）を記憶する手段を備え、上記第１
    の手段の出力に接続された入力を有し、選択された基数
    によつて減少された上記メツセージデータの２乗された
    値を示す信号を出力に供給する第１のモジユロ乗算手段
    であつて、この第１のモジユロ乗算手段の出力は、上記
    第１の手段が上記符号のない大きな値の整数である基数
    （Ｍ）によるモジユロ演算の２乗の連続を出力できるよ
    うに、上記第１の手段の入力に接続されている第１のモ
    ジユロ乗算手段と、 上記整数である指数（Ｅ）の値を受信する１つの入力、
    および上記第１の手段の出力に接続された他の１つの入
    力を有しているゲート手段と、出力および与えられた２
    進データを受信する入力を有し、選択されたモジユロ演
    算の２乗の積を示す計算結果を記憶する第２の手段と、 上記与えられた基数を記憶する手段を備え、上記ゲート
    手段に接続された第１の入力、および上記第２の手段の
    出力に接続された第２の入力を有し、上記ゲート手段に
    より制御される上記第１および第２の手段に記憶された
    値の積を示す値を出力する第２のモジユロ乗算手段であ
    つて、上記積は基数によつて減少されたものであり、上
    記第２のモジユロ乗算手段の出力は、上記第２の手段が
    上記通信チヤンネルを介した伝送のための上記モジユロ
    演算の計算結果である符号のない大きな値の整数（Ｃ）
    を記憶できるようにするために、上記第２の手段の入力
    に接続されている第２のモジユロ乗算手段とを具備する
    暗号装置。
17. （１７）上記第１のモジユロ乗算手段は上記選択された
    基数によつて減少された上記メツセージデータの上記２
    乗された値の部分積を記憶する部分積レジスタ手段を具
    備し、最大および最小有効ビツトに従つて上記値を記憶
    することができる特許請求の範囲第１６項記載の暗号装
    置。
18. （１８）上記第１および第２のモジユロ乗算手段は、上
    記部分積レジスタをそれぞれ時分割するように構成され
    ている特許請求の範囲第１７項記載の暗号装置。
19. （１９）上記第１および第２のモジユロ乗算手段に接続
    された出力データ線を有し、上記符号のない大きな値の
    整数および上記与えられた２進値を出力し、さらに上記
    第１および第２の手段のそれぞれの乗算を制御するため
    に、上記第１および第２の手段に一連の指令を送信する
    マイクロプロセツサを具備している特許請求の範囲第１
    ６項記載の暗号装置。
20. （２０）符号のない大きな値の整数をモジユロ演算の基
    数（Ｍ）として符号のない大きな値の整数（Ｂ）に符号
    のない大きな値の整数（Ｅ）（指数）を累乗する方法に
    おいて、 （ａ）上記符号のない大きな値の整数を記憶し、 （ｂ）上記記憶された値を２乗し、 （ｃ）値Ｓを得るために、基数Ｍによつて上記２乗され
    た値を減少し、 （ｄ）モジユロ演算の基数をＭとして、選択された２乗
    の積を行ない、 （ｅ）値Ｘを得るために、与えられた指数ビツト（Ｅ）
    の値に従つて、上記値Ｓによるモジユロ演算の基数をＭ
    として選択された２乗の上記積を乗算し、 （ｆ）値Ｒを得るために、上記基数Ｍによつて上記値Ｘ
    を減少し、 （ｇ）上記符号のない大きな値の整数Ｍを示す上記値Ｒ
    を記憶する ことを特徴とする累乗方法。