TW395103B - Method of effecting communications using common cryptokey - Google Patents

Description

經滴部中央標準局月工消费合作社印f. A7 ： .： - __ -B7_:__ 五、發明説明（1 ) :丨 : 〔發明所屬之:技術領域〕 本發明係關於一種，在網路上之實體間使用共同之密 j 碼鍵以進行密碼通信之共通鍵通信方法。 〔發明之背景;] 近年來，在交網等之網路上進行通信時，為了能保持 通信數據之機密而期待藉密碼文來通信之通信技術。 就這種通信技術而言，例如有著名之公開鍵方式之 Rsa，此外，有一般所周知之共通鍵通信方法，其係在網 路所包含之實體彼此間進行通信時，由傳送側之實體藉密 碼鍵來密碼化通信數據（平文）後傳送至接收側之實體、然 後由接收側之實體，藉傳送側之上述密碼鍵及共同之密碼 鍵將其擇碼成原來之通信數據者。又，在此所謂實體 (entity)，係指連接於網路之終端設備等裝置，其裝置之 使用者、其裝置之軟體、或它們之組合等，用來進行通信 之主體而言。 至於就這種通信方法來說，有一種於實體彼此間之通 信時，由設在網路之樞紐向各實體分發由總紐所生成之前 述共通密碼鍵者，已成公知。或者，例如，如由Rolf Bolm 所著之論文「NON-PUBLIC KEY DISTRIBUTION/Advance in Cryptology: Proceedings of CRYPTO '82/Plenum Pressl983,pp_231-236」，同樣由 Rolf Blok 所著之論文 「AnOptimal Class of Symmetric Key Generation Systems/Advance in Cryptology: EUROCRYPT '84/Springer LNCS 209, 1985, pp.335-338」；，或者特公平 5-48980 公報 本紙張尺度適用中國國家標準（CNS ) Λ4規格（210 X 297公鼇） .4 - (請先閱讀背面之注意事項再填寫本頁)

A7 五 發明説明( B7 經漓部中央標準局货工消费合作社印聚

或美國專利第5016276號所見，預先藉前述樞紐按各實體 =成共通密碼鍵之個人鍵，將其分發給各實 I後在通“，由各實體使本身之個人鍵，作用於通化 對方側之實體㈣有之賴符㈣，住料），藉此在進。 仃通仏之實體彼此間生成共通密碼鍵者，也已為—般所周 知0 此時，依照後者之方法，藉共同於僅由樞紐所保持之 各實體的中心算法，變換各實體之標識符，藉此來生成每 各實體之個人鍵。 &母 更詳5之，依照後者之方法，如將中心算法，例如當 做表示任意兩個標識符的變數x，y之函數p(x，y)表現時7 可將中心算法設定成P(X，y) = P(y，χ)以便具有對稱性。 而且，在此函數P(X，y)之變數χ，y中，例如，以變數y值 作為各貝體之實際標識符函數p(x，y)(以下，將此表現為 Pi⑻）’則當做各實體之個人鍵而被分發給各實體。其後 如標識符丨之實體與其他標識符j之實體進行通信時，’在標 識符i之實Μ，射做密碼鍵生成使對方叙標識符^ 用（没變數X之值為j)於自己之個人鍵pi(x)而成之p^j)。同 樣，在標識符j之實體側，當做密碼鍵生成使對方侧之標 識符i作用於自己之個人鍵Pj(x)而成之pj⑴。此時，因前 述之對稱性，而變成Pi⑴=Pj⑴，藉此在標識符；之實體 彼此間，獲得共通之密碼鍵。 可是，如依前述之共通鍵通信方法，在確保密碼通信 之安全性上，前述密碼鍵必需具備事實上無法解碼之條 本紙张尺度適用中國國家標枣（CNS〉Λ4規格U丨0X297公| ---------- n - I (諳先閲讀背面之注意事項再填寫本.頁) ir------ ·©1. 經漓部中央榍率局一^工消費"作私印t! A7 ---:;_____ B7 五、發明説明（3 ) ~~ ~-- 件。尤其是’如依前料公平5_4_號錢等中所見之 方法ί由於在所有之密碼鍵包含有規定該密竭鍵的中心算法 之關連信息，所以確保各密碼鍵之解碼之困難性則成為重 要之綠題。 然而’依知之通信方法，由於將通信數據（平文） 其本身藉密碼键來密碼化後進行通信，所以存在著可從通 ^數據之特徵等解碼密碼鍵之危險性。而且，尤其是，依 照前述特公平5-4898GH等巾所見之方法，如密碼鍵 被解碼的話，因多數實體之串通，而存在著中心算法也會 被解碼之危險性。 本發明係鑑於上述背景，而提供一種共通鍵通信方法 以便可提高系統（使用共通密碼鍵以在實體間進行密碼通 L )中之密碼鍵之對於各種攻擊之安全性。 本發明之目的更在於提供一種共通鍵通信方法，以便 在某系統一一即，對各實體之固有標識符施予共同於各實 體之秘密算法，以生成一用來生成通信時之共通密碼鍵的 秘也'個人鍵之系統--中，可提高對於包括中心算法在内 之各種攻打之’安全性。 〔發明之概要〕 本發明之共通鍵通信方法之第1樣態，係為達成此種 目的而於包含多數實體之網路中，在一用ί來進行通信之實 體間進行通信數據之密碼之時，在前述通信數據之傳送 侧’以隨機數數據為鍵，將該通信數據密碼化之同時，藉 則述共通密碼鍵來密碼化該隨機數數據，然後將其所密媽 本紙張尺度墒) Λ4規格（2丨0X 297公釐） (請先閲讀背面之注意事項再填苟本頁)

化之隨機數數據跟前述所密竭化之通信數據—同傳送至兮 通信f據之接收侧；在該通信數據之接收侧’則藉前述;: 通密碼鍵來譯碼前述所密碼化之隨機數數據，同 1碼之隨機數數據作為鍵，譯碼前述所密碼化之通信數 據。其特徵在於： ㈣述各《巾’從前㈣_先分發有各實體所固 有之個人鍵、：及含有用來石卞兮加f 個人鍵所含之前述隨機化 灰換成为之^識符變換算法，其中，該各實體所固有之個 人鍵，係由預先設在前述網路之樞紐，對於藉一共同於各 實體且僅由該樞紐所保持之包含帶加權函數積分變換算法 的中心算法來變換各實體所固有之標識符而成者，藉各實 體所固有之個人鍵，施予隨機化變換來生成者；使由各實 體所保持之自己之前述帶加權函數積分變換算法及個人 鍵’作用於通信對方侧之實體之標識符，藉此來生成前述 共通密碼鍵。 如依這樣的本發明之第1樣態’由於在前述通信數據 之傳送侧將隨機數數據當做鍵密瑪化該通信數據之同時， 藉前述共通密碼鍵來密碼化該隨機數據，然後將其所密碼 化之隨機數數據，跟前述所密碼化之通信數據一同傳送至 該通信數據之接收侧，所以欲解碼前述密碼鍵時之該密碼 鍵之信息’並非含在由隨機數數據所密碼祀之通信數據， 而是含在由密碼鍵所密碼化之隨機數數據。而且，由於該 隨機數數據本身缺乏特徵性信息，所以從所密碼化之隨機 數數據解碼密碼鍵之事變成極為困難。又，由於通信數據 本紙張/、賴财關家蘇（CNS ) Λ4規格（27ix 297公f )一 (請先閲讀背面之注意事項再填寫本頁) ，1Tn n - ---· #1. 經濟部中*標率局負工消舟合作社印聚 經濟部中央標牟局货工消f告作社印製 、 A7 —·-—________ B7 五、發明説明（5 ) 一 ： '一' 係藉隨機數數據來密碼化，所以也可充份確保通信數據之 安全‘而且，在通信數據之接收側，使用與傳送側共用 之密碼鍵’藉此可將前述隨機數數據譯碼，進而可將其已 譯碼之隨機數數據作為鍵，於最後譯碼所需之通信數據， 無阻地進行密碼通信。 因此，如依本發明，可提高，在實體間使用共通密碼 鍵來進行密碼通信之系統中之密碼鍵之對於各種攻打之安 全性。 此情形下，本發明之第丨樣態中，上述共通密碼鍵， 其上述中心算法預先於各實體，將配付之上迷帶加權函數 積分變換算法與上述個人鍵以使通信對方的標識符作用而 生成，而上述個人鍵’藉其上述中心算法包含上述加權函 數積分變換算法的中心算法，變換生成於各實體的固定的 標識符者。 即，前述標識符，只要為固定地用於各實體之姓名、 住址等，及，用於網路上之郵件名稱、或它們之組合者等， 且至少對於通信對方有公開性者即可。 而在此情況下，例如使用姓名作為各實體之標識符的 話’ -般而言該標識符之分散性並不佳（易產生標識符值 之分佈之偏差）’因此’藉前述具有對稱性般的中心算法 來變換該標識符而生成的各實體的個人鍵情形下，也易於 出現多數之類似者。因此，在所謂差分攻擊下，他人之個 人鍵或前述中心算法有被解碼之虞。 然而，在本發明中，如此，將含有前述積分變換 氺紙張尺度適用ϋ家標準（Cns )^格（ (誚先閲讀背面之注意事項再填寫本頁) 訂----^---------- —I i I . 五、 發明説明（ Α7 Β7 (詳立細者雖為帶加權函數之積分變換算法，有關加權函數 的思I義於後„兑明）之中心算法施予各實體之標識符，以生 成各實體之個人鍵，藉此可提高將前述積分變 ::識符而成之數據之分散性，進而可提高前述個人二 。藉此，由該個人鍵或前述中心算法之差分攻擊等 所引起之解碼變為困難，可提高密碼通信系統全體之安全 ::算=”，由於前述個人鍵中含有根據前述積分變 因此，不只將前述個人鍵，且將預先跟該 個人鍵-同被分發給各實體之前述變換算法，也一併作用 於通㈣方侧之實體之標識符，藉此可藉前 H換算法除外之算法部分(假定此部分具有前述對稱 性），來生成實體彼此間之密碼鍵。 如此’依於前述中心算法中人女&、w 明之第m能异去’ 3有積分變換算法之本發 月之第m態，作為前述積分變換算法用 葉（Fourier)變換、技並如你α , 疋用得利 換、希拉3拉斯（Laplace)變換、米雜mer)變 爾貝特⑽ben)變換等之任 ..v又状’只疋廷些稽分鐵 經 中 央 標 準 局 η X. 消 ft 合 作 社 印 Μ 換係定義在解析學的無限區間 、 行積分變換算法之標識符，係屬於者反觀’於本發”施 表現在有限區間上者（例 符之Hi之剩餘類），所以使用電腦等來積分變換標識 付之數據時m交換結果之異常分散卜。 積八=在本發明之第1樣態中，作為作用於標識符的 籍=換异法，其前述積分變換算法宜使用帶加權函數之 、异法°如此’於標識符施予積分變換時，附加加 本紙张尺度適則’國國( CNS ) Λ4^#7 210x1^^ 9 經承—部中央標準局兵工消f合作社印製 A7 ~~-_：_____B7 五、發明説明（7 ) ~ '-- 權函數’舶可防止上述之異常分散。再者，該加權函數， R要，可防止異常分散者’即可任意予以設定，所以藉含 有已附加此加權函數之積分變換算法的中心算法，來變換 標I线符而成之前述個人鍵中，變成附加有根據該加權函數 •之未知成分。其結果’該個人鍵或秘密算法之解碼變成更 々口困難，可進一步提高適用本發明之密碼通信系統之安全 性。 於這樣的本發明之第i樣態中，使用實體間的通信時 的前述隨機數數據係以一次性之隨機數數據為理想。即， 該一次性之隨譏數數據，係意味著無再現性，或者再現性 極為貧乏之隨機數數據；更詳言之'，構成隨機數數據之各 位數值之出現頻度，在任何數值均為相等，且無隨機數數 據之相關性者：；這種隨機數數據，例如，可由人類根據將 某S吾句或文章輸入電腦時之定時來生成。而且，將這種偶 然性之隨機數數據作為鍵來密碼化通信數據，又，藉密碼 鍵來密碼化該隨機數數據，藉此可使 該密碼鍵或通信數據之解碼更加困難。 在此情況下，根據前述通信數據之傳送側之實體之規 定處理，生成前述一次性之隨機數數據；更具體言之，前 述規定處理為前述各實體的藉人類來輸入之輸入操作，根 據其輸入操作之時間性定時來決定前次一 i欠性之隨機數數 據。 。如此，在根據各實體的藉人類來輸入之輸入操作（例 如輸入某文章或語句之操作）之時間性定時，生成隨機數 本紙张尺度適用中國國家標準(CNS ) Μ規格（210X297公釐） ]~~ΓΙ (請先閲绩背面之注意事項再填寫本頁)

經濟部中央樣率局負工消費合作社印¾ .A7 ___ _______ B7 五、發明説明（8 ) ~ ；- 數據下’其隨機數數據變成沒有再現性'或再現性極為貧 乏之數據，可確實地生成前次一次性之個別隨機數數據。 又’本發丨明之第1樣g中’如上述般於積分變換算法 上附加加權函;數者，在基本上應在標識符之數據區間之端 側，設定該加權函數以便值接近於「〇」，但此情形時， 本發明之第-實施態樣，宜藉前述樞紐所生成的隨機數數 據，將該加權函數決定成無法預料的模式，尤以使用—次 性之隨機數數據當做該隨機數數據為宜。在此，藉前述= 機數數據，來決定標識符數據區間之加權函數值之變化程 度（在區間之端側接近「0」之形態），藉此來進行藉由隨 機數數據之加權函數之決定t 如此，預先藉隨機數數據將加權函數決定成無法預料 之模式，使得就攻擊者而言，難以預測該加權函數，因而 可提高適用本發明之密碼通信系統之安全性，尤其是，藉 一次性之隨機數數據來決定加權函數時，可排除該Z機數 數據之再現性，因此更可提高系統之安全性。 如前所述，前述積分變換算法雖可使用各種者，但本 發明尤以使用傅利葉變換算法當做該積分變換算法為理 想。即，該傅利葉變換為可使用電腦迅速且容易進行之積 分變換，且，一般而言易產生變換結果之分散化。因此， 使用這種傅利葉變換算法作為積分變換算法，藉此可從標 識符迅速且容易生成前述個人鍵之同時，個人鍵之分散性 隨著有效地提高，可顯著地提高密碼通信系統之安全性。 又，在本發明之苐1樣態中，依前述中心算法中含有 本紙張尺度顧巾目_家轉Λ4規格（21GX297公资） ^1 - J---*--衣-- (請先閲讀背面之注意事項再填寫本頁) -訂 11 經滴部中央標率局眞工消f合作社印製 A7 --—_— ___ _B7 五、發明説明（9 ) ~ _ ~---- 積分變換算法之本發明，更宜者，由前述拖紐，對於藉該 中心算法來變換該各實體之標識符而成者，進一步藉由各 實體所固有之 一次性之個_機數數據，施予隨機化變換以生成前述個 人鍵之同時，預先向各實體分發前述個人鍵，以及由一算 法（用以否定該個人鍵所包含之前述隨機化變換之成份）及 前述積分變換算法所成之標識符變換算法，然後，使由各 實體所保持之自己之前述標識符變換算法及個人鍵，作用 於通信對方侧之標識符，《生«料通㈣鍵。 纟此，前述隨機化變換，係藉前述個別隨機數數據來 變更，一表示藉前述中心算法來變換該標識符而成者之數 據列的各位值，或者，酉己置變換該數據列、或者，將它們 組合起來處理’藉此來進行者。 依此，前述個人鍵〃除包含前述中心算法以外，更包 含有因前述隨機化變換而產生之成分。而且，此時，由於 該隨機化變換，係藉各實體所固有且對各實體不了解之一 次性個別隨機數數據（沒有再現性，或再現性極為貧乏之 隨機數數據）’來進行其變換，所以變成按各實體之個人 鍵而含有各別之偶然性成&。其、结|，可使密碼通信系統 之對抗各種攻擊之安全性，成為更加堅固者。 又，在此情況下，通信時，用來作用於對於侧實體之 標識符之個人鍵中，含有按各實體而藉各別之前述隨機化 變換來產生之成分。因此，預先向各實體分發前述個人鍵， 以及由一用來否定該成分之算法及前述積分變換算法所成 木紙張尺度適用中國國家標準（CNS ) Λ4規格（210X297公着） (請先閲讀背面之注意事項再填寫本頁)

12 經濟部中央標準^¾工消費合作社印製 A7 ___- ____B7 五、發明説明（' ~~~--- 之標識符變換算法；而在通信時，使該標識符變換算法及 個人鍵，作用於對方侧之實體之標識符，藉此在進行通信 之實體彼此間生成共通密碼鍵。 如此，在進行隨機化變換時，例如藉前述一次性之個 別隨機數數據來配置變換…表示藉前述中心算法來變換 各實體標識符而成者之數據列.藉此來進行該隨機化變 換。 更佳者，該表示藉前述中心算法來變換該各實體之標 識符而成者之數據列，宜包含多數個之無用位（b丨t);於是， 藉前述一次性之個別隨機數數據來隨機化前述無用位之 值，進而配置變換包含有該無用位之前述數據列全體，藉 此來進行前述隨機化變換。 如此，藉前述一次性之個別隨機數數據，來隨機化一 表示藉該中心算法來變換各實體標識符而成者之數據列之 無用位值，進而配置變換包含有該無用位之前述數據列全 體，藉此使攻擊者（密瑪通信系統之解碼者）不知所獲得之 數據之何處有對應於無用位之部分，且，在何處有需要之 數據’從而可提高密碼通信系統之安全性。 又’用來!進行前述隨機化變換之前述一次性之個別隨 機數數據’係根據前述各實體之一規定處理來生成者。更 具體言之’前:述規定處理為前述實體之藉助人類之輸入操 作；即’根據其輸入操作之時間性定時，生成前述一次性 , 之個別隨機數數據。 如此’根據各實體之藉助人類之輸入操作（例如輸入 本紙張尺度適用中國國家標準(~^s) Λ4規格（2]0><297公嬸) ~~^ (請先閱讀背面之注意事項再填寫本頁) .J— IJ.

,1T 辞· 五、 發明説明（11 ) A7 B7 恕滴部中央標導局男工消費合作社印11· 某文章或語句之操作）之時間性定時，來生成隨機數數 藉此使其隨機數數據變成沒有再現性，或再現性=’ 從而可確實地生成前述—次性之㈣隨機數數據。 其次’本發明之第2樣態者，係在於包含多數實體之 網路中，在-用來進行通信之實體間進行通信數據 ，時’在㈣通信數叙傳送侧，赠機«據為鍵，: 该通減據密碼化之同時，藉前述共通密碼鍵來 、 隨機數數據，㈣將其所密碼化之隨減數據料 2 碼化之通信姆-同傳送域㈣數據之純侧，: 信數據之接_，則藉前述共通密碼鍵來料前^ 化之賴數數據，㈣以其己譯碼之隨機數數據作為鍵 澤碼前述所密碼化之通信數據。 在於前述各實體中，從前述樞紐預先分發有各實 固有之個人鍵、及含有用來否㈣個人鍵所含之前述隨機 化變換成分之標識符變換算法，以作為使用積分變 時之其他實施態樣；其中該各實體所时之個人鍵，'係 預先設在前義路之樞紐，對於藉—共同於各實體且僅 該樞紐所保持之中心算法來變換各實體所固有之伊識符 成者’藉各實體所固有之—次性個別隨機數數據，施^ 機化變換來生成者。 ,依本發明之第2樣態，為生成上述之共.通密码之於； 述各實體之個人鍵，係於前述樞紐，對於藉前述中心算 (¾是假定含有具有前述對稱性之部分）來變換各實體之標 識符而成者，施予根據各實體所时且對各實體不了解: 由 由 而 隨 刖 法 (請先閱讀背而之注意事項再填寫本頁) • - u I - Γ I----- I - _ SI/ _ _____ 1 f. ^-------

,- - I— HI 丨;紙張尺度制巾_家縣7 14 - 經满部中央標準局I工消f合作社印f A7 -·~——----- ----Β7 五、發明説明（12) ~ '~~ ~ —次性個別隨機數數據（沒有再現性，或者再現性極為貧 乏之隨機數數據）之隨機化變換，而生成者，所以變成按 各實體之個人鍵，而含 有各別之偶然性成分。其結果，該個人鍵或前述中心算法 之解碼變成困難，可提高對於密碼通信系統全體之各稗種 文擊的安全性。而且’在此情況下，一如前述所說明之情 况，由於各實體之個人鍵中，含有因每各實體之各別之前 述隨機化變換而產生之成分，所以將含有用來否定該成分 之算法的前述標識符變換算法，預先跟前述個人鍵一同分 發給各實體，在通信時，使前述標識符變換算法及個人鍵， 作用於對方侧之實體之標識符，藉此可在實體彼此間生成 共通密碼鏈。又，各實體間在通信時，如同上述本發明之 第1樣態一般，以隨機數作為通信數據的鍵而密碼化之同 時’§亥隨機數數據以上述之共通密碼鍵進行密碼化，而將 這些經密碼化的數據作為在實體間的發收，因此能進行密 碼通信。 在本發明之第2樣態中，與上述本發明之第丨樣態相同 地-在各實體間之通信時所使用的上述隨機數數據以_次 性的隨機數數據為宜，也因為使用像這樣的一次性的隨機 數數據，因此要解讀密碼鍵或通信數據的話就變得更加困 難。 而在此情況下，根據前述通信數據之傳送側之實體之 規定處理，生成前述一次性之隨機數數據；更具體言之， 前述規定處理為前述各實體的藉人類來輸入之輸入操作， (請先閱讀背而之注意事項再填寫本頁) 訂 .©Ί.

經濟部中央摞準局賀工消费合作社印製 A7 B? 五、發明説明（13) 一~— 根據其輸入操作之時間性定時來诀定前次一次性之隨機數 數據I。依此，能綠實生成上述一次性之個別隨機數數據。 乂，依照本發明之第2樣態，—如前述之第丨樣態的情 況，可藉前述一次性之個別隨機數數據來配置變換，一表 不藉前述中心算法來變換前述各實體之標識符而成者之數 據列’藉此來進行前述隨機化變換。而且，更佳者，前述 表示藉前述中心算法來變換前述各實體之標識符而成者之 數據列，宜包含多數個之無用位；同時藉一次性之個別隨 機數數據，將該無用位值隨機化，進而配置變換該包含有 無用位之前述數據列全體，藉此來進行前述隨機化變換。 藉此，可更加提高適用本發明之密碼通信系統之安全性。 又，前述一次性之個別隨機數數據，係根據前述各實 體之一規定處理來生成者；更具體言之，前述規定處理為 月'J述各實體之藉人類來輸入之輸入操作；即，根據其輸入 操作之B·：}·間性疋時來生成前述—次性之個別隨機數數據。 藉此可確實地生成前述一次性之個別隨機數數據。 〔發明之實施形態〕 參照第1圖乃至第8圖，說明本發明之一實施形態。首 先，參照第1圖及第2圖’說明適用本實施形態之共通鍵通 信方法之密碼通信系統之概要。 如第1圖所示，依照本實施形態，密硌通信系統之基 本構築主體即樞紐1、及其密碼通信系統之用戶相互進行 密碼通信之實體2，係聯繫成可透過交網、個人電腦通信 網等之網路3’相互通信。該等板紐丨及各實體2’包含有： 木紙張尺度適( cns ) (T~~i6~ (讀先閱讀背面之注意事項再填寫本頁}

五、發明説明（Η ) 用來進行實際通信或數據處理之個人電腦等之電腦機器； 及該電腦機器之使用者。

I 板照运種構築在網路3上之主系統，一如第2圖所示， 參與樞紐1之各實體2(於第2圖中，以參照符號i，j.…表示 各實體2)，具有分別對應於各實體之固有標識符yi， yj ’ (詳述於後文）。此時，如i # j的話，yi关yj，而且， 在各實體2(i ’ j，·.··）’預先從樞紐1授有根據每個之標識 符yi，yj…·（以下，視需要而總稱為標識符Yn)由樞紐“斤 生成之各實體2所固有之個人鍵xi，xj，....（詳細如後文）。 再者，當在任意實體之彼此間進行密碼通信時，按各實體 1 ’ j，而各別地使用各實體i，j之個人鍵Xi，Xj來生成用 來進行其通信數據之密碼化（傳送侧）及譯碼化（接收侧）之 共通密碼鍵Kij，然後使用其共通密碼鍵Kij來進行實體i， j間之密碼通信。 在此，在詳述本實施形態之系統前，預先說明前述標 識符Yr^依本實施形態，各實體2之標識符γη係使用各實 體2之姓名 '住址、郵件地址、區域名、或將此等組合而 成者等，各實體2所固有者，而且有公開性者。又，在框 紐1及實體2之電腦機器中之標識符Υη之實際處理上，將 各標識符Υη，例如當做有限環上之剩餘類且代碼化而成 之向量數據來處理。 彳 以下，參照第3圖乃至第8圖，詳述一用來進行如上述 之密碼通信的本實施例形態之系統。 如第3圖所示’於本實施形態之系統，經過藉樞紐j來 本紙張尺度適用中國國家標準（CNS ) Λ4規格（2Ι0Χ297公釐） (請先閲請背面之注意事項再填寫本頁) 、11 經滴部中央標卒局—工消贽合作社印製 五 經消部中央#準局負工消費合作社印製 A7 B7. 、發明説明（15) ---- 生成及分發則述個人鍵Xn等之事前準備處理後，在各個 之貫體i ’ j間進行密碼通信。 依照藉由前述樞紐1之事前準備處理，由樞紐丨，於其 設立時，或者系統之更新時，首先，生成一成為用來生^ 各實體2之前述個人鍵之基本的、中心算法（次序丨）。 依照本實施形態，此中心算法，係由中心矩陣、加權 函數、及積分變換算法所構成。 在此，前_積分變換算法，係用來積分變換各實體2 之標識符Yn之數據的算法者；於本實施形態，使用傅利 葉變換（詳細為向速傅利葉變換）作為積分變換算法。就此 種傅利葉變換而言，已知有多數種，可由樞紐〗選擇其中 之種來生成：’用於本實施形態之傅利葉變換算法。又， 該傅利葉變換算法，實際上，係作為作用於標識符Yni 數據之矩陣來表現者。 又，加權函數，係用以防止傅利葉變換有限區間之數 據即標識符Yn之異常分散者；就是在標識符Yn之數據區 間之端點侧，值接近於「〇」等之函數。再者，中心矩陣 為對稱矩陣’更詳述之，為非特異之對稱矩陣。 在此情況下，使用一次性之隨機數數據來生成前述加 權函數及中心矩陣。即，如第4圖所示，在生成加權函數 及中’U矩陣時，由樞紐1，首先根據樞紐1之電腦機器之操 作員之人為操作，生成隨機數數據（次序1-1)，具體言之， 例如由操作員對於樞紐丨之電腦機器輸入適當之語句或文 早等’以電腦機器依次計測此時之輸入定時（例如各單語 本紙張尺舰财_丨轉2丨0x79-7公漦). (諳先閱讀背面之注意事項再填寫本頁}

18 A7 Β7· 經消部中央摞準局負工消費合作社印fi

五、發明説明（16 之輸入時刻或各早語之輸入時間間隔）。然後，根據其 所計之定時，以時間序列生成隨機數數據。如此生成之 隨機k數據，由於根據具有曖昧度之人為輸入操作之定時 來生成，所以事實上變成沒有再現性之偶然性者，藉此可 生成一次性之隨機數數據。 然後，如此生成了一次性之隨機數數據之後，由樞紐 之一次性随 及中心矩陣（次序υ),此時，藉上述—次性隨機數數據， 來決定標識符Υη之數據區間中之加權函數值之變化程度 (在區間之端侧接近「〇」之形態）；藉以進行加權函數之 決定，藉此決定該加權函數成無法預料的模式（pauern)。 又，該加權函數.，實際上，係用對角矩陣來表現。又，一 面確保其對稱性及祕異性，—面藉前述„次性之隨機數

數據來決找㈣之齡之值，藉此來進行巾心矩陣之決 定。 /N 由如上述所生成之中心矩陣、加權函數及積分變換算 法所成之中心算法’係於樞紐i中被秘密地保管起來，尤 其是中心矩陣及加權函數被嚴格地保管起來，以便搞紐I 之特定者以外之第三者（包括各實體2等在内）無法參照。 又，此等中心算法係共同於各實體2者。 其次，如第3圖所示，當各實體2(卜』」:)參與系統時， 樞紐1則使用如前述所生成且被保管著之中心算法或各實 體2之標識符Yn，於各實體2，生成各實體2所固有之個人 鍵Χη、及用來生成如後述共通密碼鍵问之標識符變換算 本紙張尺度顧悄mim- ( cns

19 Α7 Β7· 五、發明説明（17) 法，然後將之分發給各實體2(次序2) β 丨更詳言之’如第5圓所示，依此次序2，由樞紐〗，使 刖述傅利葉變換算法及加權函數之矩陣，作用於實體2之 標識符Yn之數據(向量數據），藉此對該標識符丫^施予加 權高速傅利葉變換（次序2_1}。進而，將前述中心矩陣乘 法於由該次序2-1所取得之向量數據（次序2_2)。此時，預 先讓前述標識符Υη之數據具備冗餘性，藉此在由次序2_2 所得之向量數據中，顯現使前述加權函數、積分變換算法 及中心矩料用於位φ (作為標識符γη用時具有意義）而成 之有用位、及其以外之多數個無用位。 一方面，樞紐1，係在跟實體2之通信（例如，實體2之 參與手續等時之通信）τ，生成該實體2所固有，而且就實 體2來說無法得知之一次性個別隨機數數據（次序2_3)。具 體言之，如同上述在決定加權函數等時生成―次性隨機數 數據之情況一般，在實體2之電腦機器上輸入使用者所有 之語句或文章’然後在樞紐侧將之依次接收，藉此由抱紐 1之電腦機器來計測該實體2之人為輸入操作之定時。接 著’根據其所計測之輪人操作之定時，生成前述個別隨機 數數據。在如此生錢職機數數財，其個賴機數數 據’跟加權函數等之生成時之隨機數數據_樣，變成沒有 再現性之偶然性者同時，變為實體2所时，藉此可獲^寻 一次性之値別_數數據。又，由於實體2無法得^成 怎樣之輪入操作定時且怎樣之隨機數數據，士，無法正確 地控制其人為輸人操作之定時，，所以實體2無法得知前述 本紙張尺度顧巾關諸率ΰ^)Λ4·(210Χ2974、£7 (請先閱讀背面之注意事項再填寫本頁) 訂 經濟部中央標準扃貞工消费合作社印敢 20 五 發明説明（18) A7 B7 fe满部十浹掠準局^.r消处合竹社印f 個別隨機數數據2。 數數^’㈣紐1 m序Μ所得之—次性個別隨機 數數據，將得自前述次序2_2之向量數據中之前述無用位 之各位值予以隨機化（次序2_4)。進而，利用上述一次性 之^隨機數數據，隨機地配置變換—將其隨機化的無用 :、則述有用位合而為一之向量數據(變更向量數據之成 :之排列。-人序2-5)。藉此把次序2_2所得之向量數據(藉 算法來變換標識符Yn者)隨機化變換。然後，生成由 該隨機變換所得之向量數據以作為實體2之個人鍵办使 用。又’上述隨機化變換，實際上，係以矩陣（不限於對 稱矩陣）表示，更詳述之，以該矩陣之轉置矩陣與倒置矩 陣相等之矩陣表現。 .又，樞紐1，係從前述一次性之個別隨機數數據、前 述傅利葉變換算法及加權函數，生成前述標識符變換算法 (次序2-6)。此標識符變換算法，係將一用來否定前述隨 機化變換成分（由前述個人鍵Χη所反映）之算法（由用來表 示隨機化變換之矩陣之倒置矩陣所表現）、前述傳利葉變 換算法及加權函數，合一（將分別表現之各矩陣予以乘法） 而成者。 之後’將對應於由樞紐1所生成之各實體2的個人鍵又11 及標識符變換算法，藉通信等事前分發給彳各實體2(請參照 第3圖之次序2) ’以上所說明之内容，就是枢紐1中之事前 準備處理之詳細者。 又’樞紐1，一如前述，經生成了各實體2之個人鍵Χη jr' 請Λ, 閲 讀 背 之 注

I

I裝 頁I 訂 本紙张尺度適州中國國家標準（CNS )八4規格（21〇χ29γ公釐） 21 五、 A7 B7 經消部中*摞準扃只工消Φί合竹·社印製 發明説明（19) , 或標識符變換算法之後，即把顯示對應於其實體2之前述 一次性個別隨機數數據或前述隨機化變換之矩陣予以抹 ( 除。乂，接收了本身之個人鍵χη及標識符變換算法之各 實體2 ’則將它們秘密地保管於本身之電腦機器之適宜存 儲器中。 如第3圖所示，俟進行了如前述一般之事前準備處理 後，在任意之實體間進行以下之密碼通信。又，在此處， 在各實體2之中，假定在實體丨，j(i关〗）間，將實體丨當做傳 送侧，將實體j當做接收側來進行密碼通信。 於此密碼通信時，傳送侧之實體i則，首先，從本身 所保持之前述個人鍵Xi及標識符變換算法、▲接收侧之實 體j之標識符yj，生成與實體j共通之共通密碼鍵Kij(次序 3)。 更詳s之，如第6圖所示，首先，在傳送侧之實體丨之 電腦機器上，使該實體i之標識符變換算法作用於接收侧 之實體i之標識符yj(將標識符變換算法之矩陣乘法於標識 符yj之向量數據。次序3])。其:欠，運算由該次序所得 之向量數據，與傳送側實體丨之個人鏈Xi(向量數據卜藉 此生成其與實體j之共通密碼鍵Kij(次序3-2)。 接收側之實體j則一如第7圖所#，在本身之電腦機 上使本身之標識符變換算法作用於傳送侧彳之實體i之標識 符（人序3 1)’進而運算其結果所得之向量數據與實體丨之 個人鍵Xj之内積（次序3-2)，藉此生成其與實體i之共通來 碼鍵Kji。 、 ^ 器 nn m In i _ ..ΪΤΓ.·' 03 ·· /cv. (諳先聞讀背面之注意事項再填寫本頁) 訂 本紙張尺度適财國國家標率（ 五 發明説明（2〇 A7 B7 經浸部中决標卑局兵二消贽合作社印4,1私

此時’在傳送側實體i獨自生成之共通密碼鍵Kij與在 接收侧實體j獨自生成之共通密碼鍵Kji變成同_。 ^卩，由傳送侧及接收側之各實體i，j，分別保持之個 人鍵Xi，Xj，係分別使前述附有加權函數之傅利葉變換算 法 ' 中心矩陣及隨機化變換，作用於各實體ij之標識符 而成的向量數據；又，由各實體i’j分別生成共通密碼: Kij ’ Kji時，作用於對方側實體j ’ i之標識符的前述標識 符變換异法’係將附有加權函數之傅利葉變換算法、及用 .来抹除每各實體i’j(反映於各個人鍵Xi，之隨機化變 換成分之舁法’合一而成者。 因此，在前述次序3-2所進行之内積運算下，可排除 每各實體i，j之隨機化變換之影響；作為該内積運結果1 得之各共通密碼鍵Kij，Kji，則等於：運算「使中心矩陣 作用於將附有加權函數之傅利葉變換算法施予各實體丨，』 之標識符yi，yj而成者（向量數據）」與「將附有加Λ權函1 ^ 之傅利葉變換算法施予通信方側之實體j，i之標識符幻， 而成者（向量數據）」之内積而成之結果。即，如將附4加 權函數之傅利葉變換算法施予標識w，yj而成之向量數° 據分別設為，y广，且把中心矩陣設為C，則幻卜⑼,） C.yi，，Kji=(yi，）.c.yj’(但，式中之下標丁係意料· 置）。 ， ' 於是，如前述’妇於中心矩陣c為對稱矩陣，所以明 顯地Kij=Kji。.因此’在各實體ij分別另外所生成之共兩 密碼鍵Kij ’如便成為-致，藉此兩實體i，】可共有共通I yi

In— nn · (詞先閱讀背面之注意事喟再填寫本頁〕 -訂 _______Λ---^— ·

適财中國國家標準（CNS ) Λ4規格（2!OX29i^lT 經？&-部中决標準而负J-消赀合作社印裝 A7 ·. . . . ' _____________ B7 五、發明説明（21) — ~~~~ ~~ ~ 密碼鍵。 一方面’於第3圖之次序3，由生成了同接收侧實體丨 之共适密碼鍵之傳送側實體i，從欲傳送至其共通密碼鍵 Kij或接收侧實體j之平文（文章、程序等）生成密碼通信電 文（次序4)。此時，該密碼通信電文之生成時，除了共通 岔碼鍵Kij以外，也可使用一次性隨機數數據。 更詳言之’如第6圖所示，當欲生成密碼通信電文時， 與前述之樞紐之事前準備處理之情況一樣，由傳送侧實體 i預先在本身之電腦機器，根據語句或文等之輸入操作之 定時來生成一次性隨機數數據（以下，稱做密碼通信用隨 機數數據）（次序4-1) ’然後將前述共通密碼鍵Kij當做原來 之鍵，密碼化該一次性之密碼通信用隨機數數據（次序4_ 2)。此時，例如藉三段構成之DES(Data Encryption Standard) 來進行此密碼化。 又’將在次序4-1所生成之一次性密碼通信用隨機數 數據（密碼化前者）當做鍵來密碼化（次序4_3)。此密碼化， 例如與次序4-2同樣，_藉三段構_成之deS來進行。 然後’把藉由次序4-2所取得之密碼化隨機數數據與 藉由次序4-3所取得之密碼文合而為一（作成1組），藉此來 生成應傳送至接收侧實體j之密碼通信電文。如此所生成 之密碼通信電文’則從實體i之電腦機器被傳送至實體j之· •電腦機器。. -又，前述密碼通信用隨機數數據，雖說每進行密碼通 信’即生成並加以更新為宜，但每進行幾次之密碼通信’ 本紙張尺度ill/ί]巾關家斜，（CNS )八4規格（210><297公釐） (讀先閱讀背面之注意事項再填寫本頁) 裝· 訂 ' . ..... A7 ^_ B7 —__ 五、發明説明（22) 始更新該密碼通信用隨機數數據（該幾次份之密碼通信時_ .使用同一密碼通信用隨機數數據）也可。， ί ' 一方面，由接收了上述密碼通信電文之接收侧實體j，

使用其與如前述所生成之實體i之共通密碼鍵Kji(=Kij)， 來譯碼密碼通信電文，最後獲得前述平文（次序5)C 即’如第7圖所示，首先，將其與實體i之共通密碼鍵 Kji(=Kij)當做原來之鍵使用，藉此將接收自實體丨之密碼 通信電文中之密碼化隨機數數據，譯碼成密碼通信用隨機 數數據(次序5-1)。接著，將其所譯碼化之密碼通信用隨 機數數據當做鍵使用，藉此將密碼通信電文中之密碼文譯 碼成平文（次序5-2)。藉此，最後由接收側實體j得知來自 貫體ί之所需平文之内容，在實體丨，〗間之密碼通信則告以 完結。 用來進行如前述一般之密碼通信處理的、各實體2之 電腦機器，係構成例如第8圖所示者。 即，各實體2之電腦機器備有：鍵盤4 ;由未圖示之 CPU、RAM、ROM等所構成之本體部5 ;及由前述個人鍵 及標識符變換算法、文章、程序等之平文、及用來存储保 持密碼通信電文等之硬碟等所構成之數據庫6。而且，在 =部5中’其用做其機能性構成者則包含：用來生成共 .通密碼鍵之共通鍵生成部7;用來進行通魏據之密碼化· 澤碼化處理之密碼譯碼處理部 ’处理0丨8 ’用來生成密碼通信用隨 $數數據之隨機數生成部9;及數據存儲㈣，其係用來 子储岔碼通信時由共通鍵生成部7所生成之共通密碼鍵或 W 尺度適 -----. (誚先閲讀背面之注意事項再填寫本頁) 丁— . *-°

D 25 五、發明説明（23) A7 B7 ^"•^"^^""^勇--1·消费"竹社印裝 由隨機數生成部所生成的密碼通信用隨機數數據等之數 據。 ·. ' I 具備這種構成之各實體2之電腦機器，係.藉如下述之 動作，來進行如前述用來密碼通信之處理。 即’在傳送側及接收側之任何電腦機器均生成共通密 碼鍵時（前述次序3)，首先，藉鍵盤4向本體部5指定欲使 用之前迷個人鍵Xn及標m符變換算法，從前述數據庫6拿 八所扎疋之個人键χη及標識符算法存入本體部5之共通鍵 生成部7。接著，籍鍵盤4，將通信對方側之標識符yn輸入 體卩5然後’由戎本體部5之共通鍵生成部7，一如前 使_符變換算法及個人鍵χη作用於所輸入之標識 符yn之數據，藉此來生成共通密碼鍵（前述次序w，㈣， …、後將所生成之共通密碼鍵存儲於數據存儲器10。 又’在傳送侧之電腦機器，藉鍵盤4,將用來生成前. 述始碼通信用隨機數數據之數據（語句或文章之輸入操作 數據）輸入本體部5 °然後’由該本體部5之隨機數生成部 :據所輸入之數據，-如前述’生成-次性之密碼通信 ::數據(别述次序4_1};將所生成之密碼通信用隨機 诚在傳送側之雹腦機器，從鍵盤4向本體部5指定數 6内〜之應傳送之平文，此時，從數據庫6取所指定之平 入㈣澤處理部^。然後，由該密碼譯碼處理部8，使 _樣存儲在數據存健5|中之丑.畜‘玄& 存 子铽器中之通岔碼鍵，來密碼化數據 〇 所存儲之密碼通信用隨機數數據（前述次序4_ 9 用 C讀先閱讀背面之注意事項存填寫本I) 訂--.— 卜紙张尺度適用中國丨 (CNS ) 規格_( 210X297公瀣 ^ 26 五 、發明説明（24 ) Α7 Β7 2) ’:同時將其密碼化隨機數數據當做鍵密碼化前述平文（前 述次，4 - 3)。如此由密碼譯碼處理部8所密碼化之密碼通 信用隨機數數據及平文，則當做總'括它而成之密碼通信電 文被保持在數據庫6後，由另__途徑傳送至通信對方侧之 電腦機器。. 。方面’由接收了上述密碼通信電文之接收側之電腦 機=，將該密瑪通信電文保持於數據庫6,其隨即被取入 於被碼和馬處理部8中，然後’由密碼譯媽處理部8，使用 數據存儲H1G中所存儲之共通密碼鍵，將密碼通信電文内 之密碼化機數數據_碼成密碼通信用隨機數數據（前述 次序5])，進而將其所譯碼化之密碼通信用隨機數據當做 鍵，把密碼通信電W之密碼化平文譯碼或原來之平文（前 述次序5-2)。如此由密碼譯碼處理部8所密碼化之平文被 保持在數據庫6。 如上述所構築之本實施形態之系統s由枢細i來生成 各實體2之個人鍵办時（事前準備處理），由於使作為積分 變換之傅利葉變換算法作用於各實體2之姓名等之標識符 yn，所以即使標識符仰本身有許多類似者，將其予以傳利 葉變換而成之數據之分散性也變為良好，進而，也可提高 將中心矩陣施予其數據而成之個人鍵办之分散性。其結 果’可使所謂來自差分攻擊㈣，樞之對於中心矩陣 等之令心算法之解碼，變成困難。 此時’作為上述之積分變換用者，雖可使用傅利葉樊 換、拉普拉斯變換、米勒變換、希爾貝特變換等，但由於 工紙張尺度適用令圃國家標準（CNS ) Λ4規桔

· H·— I I- I (誚先閲讀背面之注意事項再填寫本頁.) ---〆---〆/、.裝-------訂-.-------- .1 -I I -1 經湞部屮次柷卑灼兵-1·消费合竹社印製 A7 —______ _ B7 ~~ . 1 —- _ ___ 五、發明説明（25) 一 ~ 本貫施形態係使用傅利葉變換（詳述之，高速傅利葉變 換），丨所以可顯著地提.高如上述之分散性，且可使用電腦 機器以咼速度進行將傅利葉變換施予標識符％之運算處 理。 又，在生成個人鍵Xn時，由於當做中心算法附加加 .權函數，所以可防止將有限區間上之標識符^之數據傅利 葉變換而成之數據之異常分散，同時，就欲解碼中心算法 之攻擊者來說，除了中心矩陣、傅利葉變換算法等要素以 外，更增加所諝加權函數等之未知算法要素，因此可使中 心算法之解碼更成困難。尤其是，根據一次性隨機數數據 來生成該加權函數成為無法預料之形狀，所以可使上述解 碼之困難性更確實地加以破.保。 再者，在生成個人鍵Xn時’除了附加中心算法以外， 也將根據固有一次性個別隨機數數據之隨機化變換附加於 各實體2 ’所以在各實體2之個人鍵χη中，變成每各實體2 , 含有根據各別且相互沒有相關性之隨機化變換之成分。因 此，例如即使把多數之實體2串通起來，以期從各自保持 之個人鍵Xn解碼中心算法等，也變成極難以進行其解碼。 此時，尤其是，前述隨機化變換，係使傅利葉交換、加權 函數及中央矩陣作用於標識符yn而成之數據中，將無用位 值藉一次性個別隨機數數據來隨機化，然後將該無用位與 ' 有用位合一以進行配置變換者，所以無法得知由該隨機化 ' 變換所獲得之個人鍵Xn之數據中那一部分為對應於無用 位者，從而可使上述之解碼更加困難。又，就其解碼者來 本紙浪尺度通用中國囤家標準（CNS_)八4規格（210X297公釐)~ '~~' ------ ' -28 - (諳先閲讀背面之注意事項再填寫本頁} - J - I - -I - ! - : —.1— ---I - - - I 1 -'"ίν"^-I I -- -- ---- 11 Tw 1^1 I I. .---I - -- I n - !*1 - - - ml · 0¾ 、一=口 /¾ 經滴部中劣梯準局貝-1-消贽合作社印？々 A7 ----^~B7 五、發明説明（26) " ^ 说’變成為了完全攻破本實施形態之系统，而必須從個人 鍵Xn丨等之數據，解碼中心矩陣、加權函數、傅利葉變換（積 分變換）、及隨機化變換共四種類之算法，但這種解碼， 事實上’完全無法達成。 又，依本實施形態之系統，為了在密碼通信時生成共 通毪碼鍵，而必需預先把含有用來否定由該隨機化變換（被 個人鍵Xn所反映）所產生之成分的算法，跟個人鍵一同 分發給各實體2。然而，由於該標識符變換算法，係合成 用來否定由隨機化變換所產生之成分的算法、傅利葉變換 异法及加權函數而成者，所以極難以從該標識符變換算 法，將構成樞紐1之中心算法之隨機化變換算法、加權函 數、.傅利葉變換算法’個個地予以解碼。 因此，如依本發明，事實上不可能從各實體2之個人 鍵Xn等，解碼在其系統之安全上最重要的抱紐丨之中心算 法。 又，在任意之實體i，j間進行密碼通信時，由於並非 使用共通密碼鍵Kij來密碼化平文其本身，而是把不具偏 頗特徵性之一次性密碼通信用隨機數數據當做鍵密碼化該 平文，同時使用共通密碼鍵Kij來密碼化當做用來譯碼其 密碼化平文之鍵的密碼通信用隨機數數據，所以即使第三 者授文所密碼化之通信數據，也不，易從其逋信資料解碼共 .通密碼鍵Kij。而且，由於難以解碼該共通密碼鍵Kij，故 • 第二者難以取得該共通密碼鍵Kij所含之各實體2之個人鍵

Xn之k息’及該|個人鍵Xn中所含之中心算法之信息。至 本紙張尺度Μ /1]巾ϋ (繂_ ( CNS > Λ4規格（210X297公釐1 (請先閱讀背面之注意事項再填寫本頁) V裝- 訂 經消部中决摞準局β-τ消贽合竹.#印$,- A7 一———^—__一 五；發明説明（27) 於前述平文，由於把密碼通信用隨機數數據當做鍵來密瑪 '化該卞文，所以也可確保該平文之機密性。 因此’如依本實施例，可提供一種抗拒各種攻擊的高 安全性之後碼通i系統。而且，在任意之實體丨，j間進行 密碼通信時，各實體i ’ j僅使自己之個人鍵xi，Xj及標識 符變換算法，作用於對方侧之標識符yi，yj，即可在沒有 樞紐1之干預及沒有實體i，j彼此間之事前連絡等下生成 共通密碼鍵.Kij以作共同所有，所以不但安全性高，·且可 提供一種簡易且高廣泛應用性之密碼通信系統。又，在生 成如上述共通猶碼練後’.由標識符yn扮演重要之角度 方面’與見於A. Shamir之論文「Identity-Based Cryptosystems and Signature Schemes/Advance in Cryptology： Proceeding of CRYPTO -84/Spriger LNCS 196, 1985, pp.47-53」之想法相同。 其-人’就本實施形態之系統的、更理論性之有效性說 明之。 本糸統，係運真各貫體2之個人鍵，進而根據線性變 換來進行用來算出共通密碼鍵之運算者。今就此線性變換 說明如下。 首先’假定Xif為在f人之實體2間生成共通密碼鍵時 之貫體i之個人鍵。此時，用以構築上述線彳性變換之—般 想法為：任意選擇f輸入對稱變換g(f個之變數之函數，且 .. 具有對稱性者）；將實體i之個人鍵Xif，當做對於實體土之 標識符yi可滿足XifU_，..·.！： f〇/0_)=g(yi，I： ，· 本紙張尺度適用中國國家標準（CNS ) Λ4規格（210X297公釐） (錆先閱讀背面之注意事項再填寫本頁) — ίίιίιιιΒ^!---- 、1Τ

發明説明（28) 等之f-1輸入變換來決定。在 .^ m + ，下彳示之¥係顯示任意標 I識付之變數。在此情讶f t . ( ，上述線性變換顯現出好像f輪 私入對稱變換g之核依從多重 ^ m 菫線丨生變換重線性變換）一般； 此線性變換，基本上被+ 、 I上破叱羲於有限體上之線性空間，而被 一般化成環上之剩餘類。 本系統係以f=2為例時夕盎从私 . 巧1幻¥之系統者’上述之線性變換係 疋義如下。 在此，於以下之說明時，將屬於框紐i之實體之集组 設為E，將標識符之集組钟 ΚιΜ?αΧ、_ … '、 °又為，及將共通密瑪鍵之集組設 為Κ(參照請）。又，將Q設為具有單位元之可換環；射 設為Q上之位（digit)m之剩餘類；將κ設為Q上之位h之剩餘 煩*將J，K之凡.分別設為m'縱向量' h'縱向量。又，如〇 為予段（field)的話，j，K分別為維元爪咄之線性空間。又， 位m等於標識符之總數。 又，將R設為「構成從1向J之變換（mapping)」的線性 變換，以下稱做等同變換。此等同變換；如與前述實施形 癌之系統對照的話，基本上相當於將附有加權函數之傳利 葉變換（積分變換）施予標識符之數據的變換，進而，如後 述可擴充至前述隨機化變換也包含在内之變換。 以上述者為前提’首先，從；一（以j之兩個元之組為要 素的集組）任思選擇向矣通密碼鍵之集.組K的對稱Q級多重 線性變換（2輸入對稱變換）g : j—— κ，並加以決定之，此g 係相當於，為從分別等同變換任意兩個標識符者，生成對 應於它們之標識符的共通密碼鍵，而進行之變換。 本紙張尺度適州中國國家標準（CNS ) Λ4規格（2丨0X297公楚） -----...--'--· ___ "" (誚先閱讀背面之注意事項再填寫本頁) -δ 經璃部t决標準局負T,消贽合竹社印絜 經淖部中夾標準局男工消费合竹社印製 A7 B7 五、發明説明（29) 又’對於所授與之某標識符yi()，決定Q上之h行m 列之矩陣Xi ’以便滿足Xi · U U )。在此，β為

I Q上之任意之m-縱向量，且為j之元（以下’同）。 再者，對於所授與之某yi()，構成丨輸入變換；^($ )， 以便成為Xi( · R( Π(但f為I之任意元。以下同）。 此Xi( f )就是對於實體i之個人鍵；該個人鍵Xi(f )， 係使用前述矩陣Xi將1輸入變換Vi定義為VRu^xi· π 時，用下式來表示。

Xi( f ) = Vi(RCE) 又，當植紐:有多數個時，Vi( β W中之「Xi、 之部份’即置換於每各樞紐決定如上述之矩陣Xi之總和。 當如此定義個人鍵Xi時，由前述之事可易知，對於任 思貫體a，b ，成為Xa(yb) = Xb(ya)。即，如實體a，b分 別將對方侧之標識符yb，ya輸入各個人鍵Xa，Xb的話， 可獲件共通密碼鍵Xa(yb) = Xb(ya)。 又’即使選擇多變數多項式以替代前述多重線性變換 g ’也包含在本系統之線性變換之適用範圍内。此理由係 在於：任意多項式可藉未知數之集組之適當變換來置換於 線性多項式’以及那樣之變換可吸收在等同變換R中等之 二事上。 其次：說明本發明之線性變換之執行if生能及等同變換 R之角色。 對於任意之變換A，將Cd(A)、Ce(A)分別設為變換A 之複雜度、及變換A之評估之複雜度。此時，對於前述之 本紙張尺度適巧中國國家標準（CNS ) Λ4規格（2丨〇'〆297公釐） (請先閲讀背面之注意事項再填寫本頁) 、玎丨----丨^---- Α7 Β7 五、發明説明（30 ) 變換Xi、R、Vi，可成立如下之關係式。

Cd(Xi) = C：d(R) + Cd(Vi) j

Ce(Xi) S Ce(R) + Ce(Vi) 在此情況下，如假定顯示個人鍵之變換Xi之輸入(標 .識符係用w[bit]來記述的話，就變換％之記述之複雜度 Cd(Vi)成立

Cd(Vi) = h · m · w[bit] 之關係式。又，就變換Vi之記述之複雜度匚以乂丨），成立 Ce(Vi)—= 〇(h.m)[Q-運算]· 之關係式。在此，0(h · m) [Q_運算]係意味著在可換環Q 上之m之次序（order)，此值即大概可由〇(w2)[bip^換]， 即’ w2之次序來評估’而且，選擇小可換環q(例如力、口 了字段GF[2])時，Ce(Vi)變為低者。 因此，變換Xi之記述之複雜度Cd(Xi)及評估之複雜度 ce(xi)，係有賴於等同變換R之記述之複雜度cd(R)及評估 之複雜度Ce(R)之處甚多。 在此，就欲攻破系統之一個或多數個實體丨，分別利 用各個人鍵Xj之情況，考察如下。 無庸疑義，將本系統完全攻破之事，係意味著決定該 多重線性變換g:J_—K事者。此時’為了完全攻破系統 而必需要借枢紐之協力，或者，借跟多重線性變換g之位 (digit)同數（這是大致等於標識符之總數之位）)之實體 . 之協力，但此事，實際上，卻為不可能之事。 再者，就藉-部分之實料Μ其它實^人鍵沿 本紙張尺度適州中國國家標準（（:NS ) Λ4規档（ («先閱讀背面之注意事項再填寫本頁} '裝 訂 33 A7 B7 五、 經滴部中々、標"扃吳-τ·消費合作社印製 發明説明（31 ) 之可能性考察如下。關於此問題，一如以下所述，由等同 變換R來擔負重要之角色。 I, 首先’所謂「即使由實體全體之集組E之部分集組b 之所有貫體來協力’使它們之實體j分別使用各個人鍵Xj 之全體Xj | jeB ’也為了決定集組b之個人鍵幻而無法獲 得有用等之信息」，係意味著跟所謂「就E_B内之各實體i 而言，等筒變換R(yi)係從B内之實體j之各等同變換R(yi) 全體R(yi) | jeB，線性獨立}」章同值。因此，本系統之 線性變換之彳s息理論安全性，可歸結於集組{R(yi) I i ) 之任意部分集組U為線性獨立。於是，在線性變換與線性 代數學之排列組合間有密切之關係；尤其是，在評估線性 變換之女全性上，必需考察代碼字2之集組；此代碼字z係 使用由m行η列（在此，n##E=實體e之總數）之奇偶校驗矩 陣H=(R(yl)’….，R(yn)所定義之線牲代| η . ζ=0}，即，使用其與奇偶校驗矩陣Η之積成為零向量之可 換環Q上之η-縱向量，來表現者。從而可知，所謂存在著 加重平均（Hamming)重量比s之代碼字z( eLR)等之事，係 意味著與在s-1個之實體j之協力下，可引導特定實體丨之個 人鍵Xi之事同值。 .—方面，一如下述，將等同變換R個別化(將等筒變 換作成各實體所固有者），藉此即使多數之贅體串通起來,， 也難以攻破系統。即，如果對於欲攻破系統之各實體』(j e B ) 之等同變換R(yi)之集組{ R(yj)丨jeB)，其他實體i之等 同變換R(y i )為線性從屬，且R(yi)=；ECj . R(y〗)(但，cj Μ氏張尺舰财關家轉(~^ΤΧ4規格（2丨〇χ297公楚 (誚先閱讀背面之注意事項再填寫本頁) 丁 、-° 34 五 '發明説明（32) A7 B7 經域部中央標淖局萸.T消贽合竹社印f- 為適當之係數）的話，從前述之個人鍵之定義可知，就實 體i，個人鍵及實體j(jeB)之個人鍵Xj，成立Xi=I：Cj · X j之關係。因此.，欲攻破系統之各實體』之集組B變成可 輕易得知其他實體丨之個人鍵Xi。然而，若把等同變換r 個別化時’該變換R為各實體所固有者，所以不易看出 具有可解碼其他個人鍵Xi之標識符yi的實體卜換言之， 集組B之實體·），無法從它們所持有之個人鍵Xj等之信 息，得知可解碼那一實體i之個人鍵Xi。又，反之，對 於具有所授與之標識符yi的實體i，也不易看出含有可解 )碼其個人鍵Xi之標識符的集組B。換言之，即使特定具 有欲解碼的個人鍵Xi之實體，也無法得知為了解媽其個 人鍵Xi而串通何實體彼此間才好之事。如此，將等同變 換R個別化之事，在提高系統之複雜度之理論安全性上， 在本質上為不可忽視者。 如此’將等同變換R個別化的話，可選擇各種線性 變換’不過’基本上可大別為二範疇。 其—例為：使用其對應線性代碼以成為周知之代數 學或代數幾何學代碼之等筒蠻換 寸间變換K，另—例為：將等同變 換R按各實體個別地隨機化。 此％ ’依照前者之方法，如為 她 如為了女全性而將標識符之 w數m作成大總數的話， 乂商要之數據有丨變成大規模者 (向。例如，假定源要素為α，Q=GF⑷：方^字段； 又，假定h=】，^為“之！：乘（ 假定以i：、r 、s pα);再者， …j。由於此等同變換 (諳先閱讀背面之注意事項再填疼本頁) 「丨_ — Ie裝- --i,^ .------1C — .

.I~I P 35 &部中^<標準局負工消费合作社印裂 Α7 . Β7 五、發明説明（33) R不具單向性，而非為嚴密之線性變換，但卻相當於前述 之 R.丨 Blom 之論文「An Optimal Class of Symmetric Key

Generation System」中所提案之線性變形，線形代碼lR 則相當於所謂Reed-Sol〇mon碼。而且，依照此方法，網 路内之實體總數η必需小於Q=GF(q)中之q，例如，n=1〇 u 時，如適用此方法的話，最小之Q則變成GF(24〇),而必 需要極為大規模之數據量。 反觀，將等同變換R按各實體個別地隨機化之後者 之方法’係於前述之實施形態中，藉前述隨機化變換來實 現化之方法者；依照此方法，標識符之總數m(在本系統， 尊於貫體之總數η)即使為大數，也可實現高速之處理， 且存在著用小規模之數據量即可達換 R。 在另一方面，可利用跟引導周知之漸近性Varsham0v_ Gilbert之臨界式相同之方法，獲得對應於該臨界式之如 下關係式。一 m/n+r^ φ (b/n) 但，r=m . logq(q-l) 在此’ φ係由 〇(u)=u · logq(q-l)-u · logqu -(l-u)logq(l-ti) 所定義之函數。又，上述不等式中之b為欲攻波系統之實 體J·之總數（=#B)。 上述不等式，係用來規定為攻破系統所必需之實體總 本紙張尺度適用中國國家榡準（CNS ) Λ4規格_( 210X297公釐)—" ' 一讀先閱讀背面之注意事項存填寫本頁) •1;裝------訂----- -36 五、 發明説明（34) A7 B7 數b之Es界者.> 此X楚> 不等式不成立之實體數b即意味著無法 攻破系統。 立而且’根據此不等式可知，其係存在替，即使對於任 忍m及b ’有b個之實體』同謀，也無法解瑪其他實體（ 之個人鍵Xi的等同變換R 建換及。又，也明白，等同變換尺之 個別隨機化’可在大部分之時候，一面滿足如上述之條件， 一面造成良好線性獨立之構造。 因此，本系統，可在等同變換&之個別的隨機化下， 提供高安全性之系統。換言之，本系統，係在等同變換R 之個別的隨機化下，提高該變換R之記述之複雜度Cd(R) 及評估之複雜度Ce(R)，進而，㈣個人鍵xi之記述之 複雜度Cd(Xi)及評估之複雜度以⑶），藉以來確保系紙 之安全性者。 (誚先閱讀背面之注意事項再填寫本頁) ?裝. 訂 經7&‘部中决椋準局月工消贽合竹社印取 例如’假定 Q=GF(2)，m=8‘192，h=64 時， 卿卜6聯帅此時，可藉16〇阶之共通密碼鍵， 在最大可含至1G12G個實體之系統上之任意兩個實體間， 道行密碼通信。而且，例如使用時鐘2〇〇顧2且32吣 之Cpu及640 Kbyte之存儲器的話，可在2〇咖以内算1出 各個人鍵。再者，只要8192值之實體不串通，即完全無 法攻破本系統；又，只要256個以上之實體 之個別隨機下Φ通’即無法獲得對於其他實體之個 任何信息。 . 又，前述之實施形態，雖除了加權函數及傅利葉變換 算法之外’更設定中心矩陣作為中心算法，但將加權函數 本紙張尺度剌中涵家標率（cnsTa4規格ΤΥιο— -------- 五 A7 B7 -消部中央椋準局貞Η消费合作社印？+ 、發明説明（35) 本身作為中心矩陣使用也可。 又，前述賓施形態，雖使用傅利葉變換作為積分變換， 但拉1 普拉斯變換、米勒變換、希爾貝特變換等，'使用其他 形式之積分變換也可。 [圖式之簡單說明] 第1圖為一構成回，顯示適用本發明共通鍵通信方法 之一實施形態的密碼通信系統之全體。 第2圖為一概念圖，說明第i圖係統之基本構造。 第3圖為一流程圖，用以說明第1圖系統之處理手續 之概要。 第4圖為一流程圖，顯示第3圖之次序〗之處理詳細。 第5圖為一流程圖，顯示第3圖之次序2之處理詳細。 第ό圖為一流程圖’顯示第3圖之次序3及次序4之 處理詳細。 第7圖為一流程圖’顯示第·3圖之次序3及次序5之 處理詳細。 第8圖為一方塊圖，顯示用以處理第6圖及第7圖之 電腦機器之構成。 本紙張尺度適财關家辟（⑽）規格（2U)X297公餐） (請先閱讀背面之注意事項再填寫本頁) HI—— τ II —1 I— . --e先 38 經濟部屮次#卒局员T,消費合作"印製 A7 ____. B7五、發明説明（36 ) 元件標號對照 j 1…· ·樞紐 I 2 · · * ·實體 3 · · · ·網路 4 · · _…鍵盤 5。· “本體部 。…〜數據庫 7" ·•共通密碼鍵生成部 8…·。密碼譯碼處理部 9……隨機數生成部 10……數據生成部 E·。。·實體之集組 I…。·標識符之集組 K "。·共通密碼鍵之集組 Xu…»個人鍵 yn標識符 KiLKji。》…共通密碼键 yl·…·主體i之標識符 y j · · ·主體j之標識符 Xi.…實體i之個人鍵 Xj··…實體j之個人鍵 i……傳送側實體 , j……接收側實體 (請先閱讀背面之注意事項再填窩本頁) -- \—~· -3·

C 本紙張尺度適用中國國家標隼（CNS ) Λ4規格（2丨0X297公釐）

Claims (1)

1. A8 B8 C8 D8 經濟部中央揉準局員工消費合作社印製 申請專利範圍 1. 一種共通鍵通作古、， Qk，係於包含多數實體之網路中，在 」來進仃通信之實體間進行通信數據之密碼之時，在 則述通L數據之傳送側，以隨機數數據為鍵，將該通信 數據密碼化之同昧 +. 守’藉别述共通密碼鍵來密碼化該隨機 數數彳f S後將其所密碼化之隨機數數據跟前述所密瑪 數據—同傳送至該通信數據之接收側；在該通 虞之接收侧，則藉前述共通#碼鍵來譯碼前述所密 碼化，隨機數數據，同㈣其己譯碼之隨機數數據作為 鍵澤碼則述所密碼化之通信數據。其特徵在於： 於則述各實體中，從前述樞紐預先分發有各實體所 有之個人鍵、及含有用來否定該個人鍵所含之前述隨 機化變換成分之標識符變換算法，其中，該各實體所固 有之個人鍵’係由職設在前述網路之椹紐，對於藉一 共同於各實體且僅由該樞紐所保持之包含帶加權函數積 分變換算法的中心算法來變換各實體所固有之標識符而 成者’藉各實體所H]有之個人鍵，料隨機化變換來生 成者；使由各實體所保持之自己之前述帶加權函數積分 變換算法及個人鍵，作用於通信對方侧之實體之標識符 ’藉此來生成前述共通密碼鍵。 2·依據申請專利範圍第1項所述之共通鍵通信方法，其特 徵為： ， 、 刖述隨機數數據為一次性之隨機數數據。· 3.依據申請專利範圍第丨或2項所述之共通鍵通信方法，其 特徵在於： ’、 -----V 裝----------訂 (請先閲讀背面之.注意事項再填窝本育) ,

   A8 B8 C8 D8 申請專利範圍 前述隨機數數據，係根據該通信數據傳送侧之實體 之—規定處理來生成者。 4·依據申請專利範圍第3項所述之共通鍵通信方法，其特 徵在於： 前述規定處理係前述實體之藉人類來輸入之輸入操 作’根據其輸入操作之時間性定時，決定前述一次性之 隨機數數據。 5.依據申請專利範圍第1項所述之共通鍵通信方法，其特 徵在於：：_ 月j述加權函數.，係由前述樞紐中所生產的隨機數數 據決定成無法預料之模式。. 依據申叫專利範圍第5項所述之共通鍵通信方法，其特 徵在於： 生成前述加權函數之前述隨機數數據為一次性之隨 機數數據。 7. 依據巾請專利_第1項所述之共通鍵通信方法，其特 徵在於： 前述積分變換算法為傳利葉變換算法。 8. 依據中％專利圍第丨項所述之共通鍵通信方法，其特 徵在於： 由刖述樞紐’對藉前述中心’算法來變換前述各實體 之標識符而成者’進—步藉由各實體所固有之-次性個 別隨機數數據’施予隨機化變換以生成前述個人鍵之同 夺預先向各貝體分發前述個人鍵，以及由一算法（用 桃⑽適用中國國家 (請先閎绩背面之注愈事項再填寫本頁) 1'"m 、ν-° 經濟部中央標準局員工消費合作社印製 申請專利範圍 經濟部中央榡準局員工消費合作社印製 ::該個人鍵所包含之前述隨機化變換之成分)及前 a 口權函數積分變換算法所構成之標識符變換算法. i 吏由各實體所保持之自己之前述標識符變換算法及個人 通密2於通信對方側之實體之標識符，以生成前述共 9. :::請專利範園第8項所述之編 一糟前述—次性個別隨機數數據來配置變換，—表示 攄列述:〜法來變換前述各實體之標識符而成者之數 |，藉此來進行前述隨機化變換。 10. =中請專利範圍第9項所述之共通鍵通信方法，其特 徵在於： - 表不藉刖述中心算法來變換前述各實體之標識 成者之數據列’係包含多數個之無用位；於是， 月』述、*性之個別隨機數數據來隨機化前述無用位 #進而配置變換包含有該無用位之前述數據列全 _，藉此來進行前述隨機化變換。. =申π專利轨圍”項所述之共通鍵通信方法，其特 徵在於： 前述-次性之個別隨機數數據，係根據前述各 之一規定處理來生成者。， 請㈣範圍第Η項所述之共通鍵通信方法 .特徵在於： ' \規定處理為前述各實體之藉助人類之輸 實 其 入操 請 閎 讀， 背 © 之 注 2 i 裝 订 ^尺度適用 六 、申請專利範圍 A8 B8 C8 D8 經濟部中央標率局員工消費合作社印製 作；根據其輸入操作之時間性㈣，生成前^# 4 之個別隨機數數據。 ㈣一種共通鍵通信方法s係於包含多數實體之網路中， I在-用來進行通信之實體間進行通信數據之密碼之時s 在前述=信數據之傳送側，以隨機數數據為鍵\將該通 1+數據密碼化之同時’藉前述共通密碼鍵來密碼化該随 機數數據》然後將其所密碼化之隨機數數據跟前述所 .㈣之it信_ -同傳送至該通餘據之純侧；在… t 數據之接收侧，_前述共通密碼鍵來譯碼前述所 密碼化之機數數據，同時以其己譯碼之隨機數數據作 為鍵#碼别述所密碼化之通信數據。其特徵在於： 在於别述各實體♦，從前述樞紐預先分發有各實體 左•有之個人鍵、及含有用來否定該個人鍵所含之前述 =化變換成分之標識符變換算法，以作為使用積分 、算法4之其他實施態樣，·其中該各實體所固有之個八 ，係由預先設在前述網路之樞紐，對於藉—共同於各 僅由該樞紐所保持之中心算法來變換各實體所固 有之標識符而成者’藉各實體所固有之—次性個別隨機 1致數據，料_化變換來生成者。 K ^據中請專利範H1第13項所述之共通鍵通信方法， 特徵在於、 . 丨 h述卩思機數數據係一次性之隨機數數據。 =據申請專圍第13或14項所述之共通鍵 法，其特徵在於： 密 該 變 人 其 方 -I I In I- i 4H\. HI n — ,箭先聞读#^之法意事項^填寫本買) 訂 Λ: 申請專利範圍 A8 B8 C8 D8 經濟部中央標準局員工消費合作社印製 别述隨機數數據，係根據前述通信數之發信側之各 實體之一規定處理來生成者。 16·依據中請專利範圍第15項所述之共通鍵通信方法，其 _特徵在於： 前述規定處理為前述各實體之藉助人類之輸入操作 ’·根據其輪入操作之時間性定時，生成前述一次性之隨 機數數據。 17.依據申請專利範圍第13項所述之共通鍵通信方法，其 特徵在於： 、 藉前述一次性個別隨機數數據來配置變換，一表示 藉剛述中心算法來變換前述各實體之標I符而成者之數 ，列，藉此來進行前述隨機化變換。 W據申請專利範圍第17項所述之共通方法，其 特徵在於： 一 '、 一表示藉前述中心算法來變換前述各實之標識符 而成者之數據列，係包含多數個之無用位；於是，藉益 述—次性之個別隨機數數據來隨機化前述無用位之值 進而配置變換包含有該無用位之前述數據列全體，藉 來進行前述隨'機化變換。 依據申請專利範圍第13項所述之共信方法，立 特徵在於： ，’、 前述一次性之個別隨機數數據，係根據前述各實體 之—規定處理來生成者。 ^ 2〇·依據申請專利範圍第19項所述之共通鍵通信方法，其 此 (請先閲讀背面之注意事項再填寫本夏) 「' 裝I -- 、言 •10. 本紙張纽適用中國國家樣準（㈣）从規格（2ι()χ297公缝） 44^ ^ A8 r B8 C8 D8 々、申請專利範圍- 特徵在於： 前述規定處理為前述各實體之藉助人類之輸入操作 :根據其輸入操作之時間性定時，生成前述一次性之個 別隨機數數據。 (請先閲讀背面之注意事項再填寫本頁) 'ITIn 1........ 經濟部中央標準局負工消費合作社印製 本紙張尺度適用中國國家標準（CNS ) A4規格（210X297公釐厂 -45 -