JPH035101B2 - - Google Patents

Description

【発明の詳細な説明】 本発明はデイジタル伝送系において、目指す受
信者以外にメツセージを盗用されないようにメツ
セージをデータ系列に変換し、あるいは変換され
ているデータ系列をもとのメツセージに復元する
ための符号変換器に関する。

デイジタル伝送系においてメツセージを傍受さ
れないようにする著名な方法として次の方法があ
る。暗号鍵を（ｎ、ｅ）、解読鍵を（ｎ、ｄ）と
する。ここでｎ、ｅ、ｄはある定められた方法に
よつて得られる正整数である。送信側ではｎ未満
の任意の非負整数の入力データのａをa^eをｎで割
つた余りに変換して送信し、受信側では暗号化さ
れたデータｂをb^dをｎで割つた余りに変換して復
号する。ｎ、ｅ、ｄを求める方法、アルゴリズム
の正当性、秘匿性については文献コミユニケーシ
ヨンズ・オブ・ザ・エーシーエム
（Communications of the ACM）21巻２号1978
年１月120〜126頁に詳しく載つているので省略す
る。暗号化も復号化も同一種類の変換で、入力ｘ
に対してx^mをｎで割つた余りを出力するもので
ある（ｍは正整数）。従来、入力ｘに対してx^mを
ｎで割つた余りを出力する符号変換器は、内部に
含む乗算器の処理時間の２×〔log₂m〕倍の処理
時間を必要とし、全体の処理時間に占る割合が大
きいものであつた。（前記文献参照）。〔 〕は整
数部を表わす。

本発明の目的は処理時間が短く内部に用いる乗
算器の処理時間の〔log₂m〕倍で済み、かつ装置
規模がそれほど大きくない符号変換器を提供する
ことにある。

以下図面を用いて本発明の構成および動作原理
を詳細に説明する。

第１図は本発明の一実施例を示すブロツク図で
ある。図において１０１は入力端子、１０２は出
力端子、１０３は連続した複数個の入力データを
ある定められた時間だけサイクリツクに繰り返す
データ巡回器、１０４は前記データ巡回器１０３
からのデータと後記自乗器１０６からのデータを
両者の積またはいずれか一方のデータに変換する
選択的乗算器、１０５は前記選択的乗算器１０４
からのデータをあらかじ定められた正整数ｎで割
つた余りに変換する剰余器、１０６は前記剰余器
１０５からのデータをｎを法として乗する自乗器
である。ここでデータｘをｎを法として２乗した
結果は、x²あるいはx²をｎで割つた余りを意味す
る。

第１図を用いて本発明の動作原理を説明する。
ｍ、ｎをあらかじめ定められた正整数とし、ｍと
２進数展開した結果を式(1)とする。

ｍ＝2ⁱ⁰＋2ⁱ¹＋……＋2^iK (1) ここでｋ、i₀、i₁、……、i_Kは非負整数で式(2)
をみたす。

i₀＞i₁＞……＞i_K (2) タイミングを０、１、２、…で表わす。説明を
簡単にするため選択的乗算器１０４、剰余器１０
５、自乗器１０６は全て１つのタイミング間隔時
間で処理できるものとし、データ巡回器１０３の
出力系列の周期を３つのタイミング間隔時間と仮
定する。入力端子１０１に印加される入力データ
系列をa₀、a₁、a₂、…とする。データ巡回器１０
３はa₀、a₁、a₂を受けてサイクリツクにa₀、a₁、
a₂、a₀、a₁、a₂、…、a₀、a₂をi₀周期出力し、そ
の次はa₃、c₄、a₅を入力してサイクリツクにa₃、
a₄、a₅、a₃、a₄、a₅、…a₃、a₄、a₅をi₀周期出力
する。以下同じことが繰り返される。このとき出
力端子１０２にはa^m ₀、a^m ₁、a^m ₂、a^m ₃、…をｎで割
つた余りが出力されることを示す。このためには
データa₀がどのような処理を受けて出力端子１０
２に出力されるかを追つてゆけば十分である。選
択的乗算器１０４はタイミング０、１、２でデー
タ巡回器１０３からのデータをそのまま通過さ
せ、タイミング３（i₀−i₁）、３（i₀−i₁）＋１、３（
i₀
−i₁）＋２、…、３（i₀＋i_K）、３（i₀−i_K）＋１、３
（i₀−i_K）＋２でデータ巡回器１０３からのデータ
と自乗器１０６からのデータを積に変換し、その
他のタイミングでは自乗器１０６からのデータを
そのまま通過させるものとする。タイミング０で
a₀は選択的乗算器１０４をa₀のまま通過し、タイ
ミング１でa₀は剰余器１０５をa₀のまま通過し、
タイミング２でa₀は自乗器１０６を通過してa² ₀
（m₀ dn）となり選択的乗算器１０４に入力され
る。m₀dnはｎを法とすることを意味する。タイ
ミング３（i₀−i₁）で選択的乗算器１０４によりデ
ータ巡回器１０３からのデータa₀と自乗器１０６
からのデータa₀ ^2i0-i1（modn）は積a₀ ^2i0-i1+1
（modn）に変換され、タイミング３（i₀−i₁）＋１
でa₀ ^2i0-i1+1（modn）は剰余器１０５により
a₀ ^2i0-i1+1をｎで割つた余りに変換され、タイミン
グ３（i₀−i₁）＋２でa₀ ^2i0-i1+1をｎで割つた割りは
自乗器１０６によりa₀ ^2i0-i1+1+2（modn）に変換さ
れ選択的乗算器１０４に入力される。このように
して結局タイミング3i₀＋１では乗余器１０５か
らa₀ ^2i0+2i1+…^+2iK＝a^m ₀をｎで割つた余りが出力端
子１０２に出力される。同様にタイミング3i₀＋
２、３（i₀＋１）では出力端子１０２に各々a^m ₁、
a^m ₂をｎで割つた余りが出力される。パイプライ
ン化されているので処理時間は１つの入力データ
当りほぼi₀個すなわち〔log₂m〕のタイミング間
隔時間ある。即ち、乗算器の処理時間の
〔log₂m〕で済み、従来方法より短かくなつてい
る。

第２図は選択的乗算器の一実施例を示すブロツ
ク図である。図において２０１，２０２は入力端
子、２０３は出力端子、２０４は乗算器、２０５
はロータリー・スイツチである。乗算器２０４は
入力端子２０１と２０２からのデータの積をと
り、ロータリー・スイツチ２０５は２つの入力端
子２０１と２０２及び乗算器２０４からのデータ
のいずれか１つをタイミング信号により選択出力
する。

本実施例においてロータリー・スイツチはセレ
クタにおきかえることができる。

第３図はデータ巡回器の一実施例を示すブロツ
ク図である。入力端子３０１より入力されデータ
はシフトレジスタ３０３に入れられる。シフトレ
ジスタ３０３の内容を古い順にa₀、a₁、a₂とおく
と整流子３０４はシフトレジスタ３０３の各出力
より順にa₀、a₁、a₂、a₀、a₁、a₂、…を出力端子
３０２に出力する。

本実施例において整流子はロータリー・スイツ
チやセレクタに置き換えることも可能である。

本発明において選択的乗算器、剰余器、自乗器
は等しい処理時間をもつとしたが、異なる場合で
もデータ巡回器の出力系列の周期を適当に変えれ
ばよく、また自乗器はデータｘをx²に変換するだ
けでなくさらにx²をｎで割つた余りに変換する回
路としてもよく、これらの変換は本発明に含まれ
るものである。

以上詳細に説明したように、本発明装置を用い
れば入力データ系列a₀、a₁、a₂、…に対してa^m ₀、
a^m ₁、a^m ₂、…をそれぞれｎで割つた余りの系列を
短い時間でかつ簡単に計算できるので従来技術の
欠点を除いており、デイジタル伝送系におけるプ
ライベートな通信に適用して効果が極めて大き
い。

【図面の簡単な説明】

第１図は本発明の構成を示す図、第２図は選択
的乗算器の実施例を示す図、第３図はデータ巡回
器の実施例を示す図である。図において１０１，
２０１，２０２，３０１は入力端子、１０２，２
０３，３０２は出力端子、１０３はデータ巡回
器、１０４は選択的乗算器、１０５は剰余器、１
０６は自乗器、２０４は乗算器、２０５はロータ
リー・スイツチ、３０３はシフトレジスタ、３０
４は整流子を各々示す。

Claims (1)

【特許請求の範囲】
1. １ あらかじめ定められた第１の正整数ｎ未満の
   任意の非負整数の入力データ例a₁、a₂…に対して
   あらかじめ定められた第２の正整数ｍによるべき
   乗a₁、a₂、…のそれぞれをｎで割つた余りを出力
   する符号変換器において、連続した複数個の入力
   データをある定められた時間だけサイクリツクに
   繰り返すデータ巡回器と、前記データ巡回器から
   のデータと後記自乗器からのデータを両者の積ま
   たはいずれか一方のデータに変換する選択的乗算
   器と、前記選択的乗算器からのデータをｎで割つ
   た余りに変換する剰余器と、前記剰余器からのデ
   ータをｎを法として２乗したデータに変換する自
   乗器から成り、前記データ巡回器の最終サイクル
   に、前記剰余器からのデータを出力することを特
   徴とする符号変換器。