TW200818835A - Authentication based on asymmetric cryptography utilizing RSA with personalized secret - Google Patents

Description

200818835 九、發明說明： 【發明所屬之技術領域】 本專利申請案的技術領域屬於資訊安全的「使用者認證」（user authentication)，特別是在各種數位化裝置、系統和網路有關的使用者 認證方法與系統。 【先前技術】 岔碼系統(cryptosystem)使用密碼金输(crypt〇 key)於密碼學相關

的什异上。在以非對稱式密碼學(aSymmetric crypt〇graphy)為基礎的 密碼系統中，如RSA(Rivest，Shamir, Adleman)系統，其密碼金錄是 以一把公開金鑰(pubhc key)與一把私密金鑰(p「ivate key)成對的方式 產生。使用「公開、私密麵對」的方式決定了兩種應用。—種是使 用私密金錄作為-把簽章麵，在數健息上產生數位簽章，並且使 =公開金猶為—把驗證金鑰，以驗證某—數值是否為—正確的簽章 穷文而Cl應用ί使用公開金鑰作為加密金鑰，對明文加密轉換為 ⑴I 用私禮金鑰作為解密金錄，以將該密文解密回明文。 文的tit好的使用者必須將他的簽章金絲持機密，而一位密 秘密。儘管私鑰保持機密。因此’私密金鑰是一個 並不應該茂漏“^^ :、么開金餘有關的數值，公開金餘的揭露 開金绩轉出私密^在 。由於這種機㈣需求，從公 性所必要的條件/ 十_難，是非對稱式密碼系統的安全 兩個質數之模運算’而模運算之模數是 原因是缺少―個有效^二出，金输在計算上的困難，部份 數。在RSA中，一饼八將兩貝數的乘積分解回原來的兩個質 存在著特定的_ 密錢魅生該錢_兩個秘密質數 鑰；這種_^-；；^輪法允許使財自錄地選擇私密金 更進步限制了私密金錄的變更，私密金錄的變更 5 200818835 Λ 回溯到重新產生金錄對的過程。 下文描述RSA的背景知識。 RSA密碼系統被描述於美國專利44〇5823號以及Rjvest， Shamir 與 Adleman 所共同發表的論文：“A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, ”

Communications of the ACM，ν〇Ι·21(1978), pp.120-126。目前已經有 數個國際標準可用來教導此非對稱式密碼學，包括PKcs #i:rsa

Cryptography Standard, Nov· 1993 (ν· 15) & June 2002 (ν· 2·1)以及

,EEE std 1363-2000: IEEE Standard Specification for Public-Key • Crypt〇graphy，此兩標準的文件可分別由RSA Lab〇rat〇fies及旺E =網站上取得。這些標準文件的内容包括金鑰產生、加密、解密、簽 章產生、簽章驗證與其他相關技術的描述。 RSA的計算牽涉到模運算。模運算之定義如下：如果X與y為兩 個夤數，且若正整數z整除(x—y)，則可稱乂與乂對z進行模運算的結 果疋同餘(congruence)，以符號表示為XEy (mocj z);正整數2則稱 為同餘之模數。 ' PKCS# 1 ν·1·5所提出之RSA金鑰產生之過程，概述如下： (1) &擇一個正整數e為加密用之指數(encryption exponent)，也 稱為公開指數(public exponent)。 (2) 隨機選擇兩個不同奇質數(tw〇 〇dcJ p「jrTle numbers) p與q，使 P—1與cj~1兩者皆與e互質。 ⑶取公開之模數(publjc m〇dulus)為p與q的乘積，即㈣叫。 (4)選擇一個私密之，以符號0表示之，使 P —1與q—1兩者皆可整除dxe —>1。 一 RSA之公開指數e與模數n被用來對明文整數值⑺加密，以〇 （m〇d n)之計算得到密文整數值c，在此假設m小於η Γ另以私 密之指數d與模數n藉由mECd (m〇d n)之計算，將密文值c解密回 6 200818835 明文值m。 f有些被瑪系統中’例如ssl/tls⑼C(J|O Sockets 糾職祕，係混合 對稱式密碼學方法的加解密系統。在此混 =統中，通訊的—方—把rsa的公開金鑛—個隨機產生的 力心而另—方則使用對應的咖_麵將被加密的秘密 、A &碼金鑰’輯赋密碼學的方法進行秘密通訊〇在此- H ’又方所共用的對稱式秘密金鑰(symmet「丨c c_〇 _稱為通 離ession key) ’它是一個隨機產生·數。以上的程序稱 為^、麵的交換過程，其詳細說明，請參考丨他咖_瞻 TaskForce網站上之郎〇2246及其他相關文件。 RSA中之減缝d與模數n可被用來製作—健位簽章。首 先们數位u、㈣某-個具備碰撞阻抗特性的赫序函數(a con.s.on-resistant hash function)^M „m^^(message d_)，表不為hash(M);接著，訊息M之數位簽章可飯由 haSh(M)d(mod n)之計算得到，表示為邮⑽呢⑽）。 RSA中之公開指數e與模數n，被用來驗證某一個數值是否為一 個正確的紐簽章。假設_位驗證者_ M II SGN，其巾Μ代表 個數^息，丨|代表兩個訊息的連結，而SGN代表一個附加於Μ之 數位簽章值。首先’驗證者使用已選擇的碰撞阻抗赫序函數計算出 hash(M)，其夂，使用公開金錄(n，e)進行sGNe mocj η之計算，並將 計算所得的結果與hash(M)作比較，如果比較的結果是相等的 為一個正確的簽章。 、 早日守所用的碰撞阻抗赫序函數，必需與產生簽章的碰撞阻 抗赫序函數相同，即符號以讣所代表的函數。 里且 產生數位线早用到赫序函數。赫序函數是一種確定性的函數(非機 200818835 f_)，其意義是錄雜㈣綠由.。使靜數 :^序函數必須具有抗碰撞的特性，這表示要找到賴不同的輸入 值來產生相同的輸出值是非常困難的。碰撞阻抗赫序函數也且有單向 示’給定^輸出值’要找到—個輸人值使其經過 出值專於該給定的輸出值，是非常困難的。除此之外，赫 幕式ΐf =、/f產^虛擬隨機輪出(pseud_dom ου_)能力的罩 U=_ask generatiQn funetiQn) ’賊妓僅給定輸出值的 ’ I __賴不可行的。在 數，供 〜、下 建°義了具備上述特性的六種不同赫序函 ： MD2'MD5'SHA-1 '3HA-256.SHA-384 赫序函數的輸出值稱為赫序值(hash ▽_)，也有稱之 ash digest) ’ 或訊息摘要(messagedigest)，或雜湊值。'… 非對稱式密碼學之應用中引發出令人關心的一個問題。一位公開 1;:二’二ΓΓ的驗證細密訊息的傳送者，該如何知 正呢;Γ欺齡也許會欺繼證者將不 公開金餘對機巧自力，者欺.編訊息傳送者使用一個偽造的 _ic-key ce_°at:力：3 ;也就疋我們所知道的數位馮嘮idinitd 賴lcate)，提供了 _個解決之道。 ]数位—（d_l 入」象的。 兒個公開金鑰憑證包含了三個主要的部份：-個公門 金錄。藉由驗證馮所有’同時保證該個體持有相配對的私密 可證明這樣的證機構之數位簽章，公開金錄之使用者則 被信賴的機構，：主要：_^certmcati—^ 成偁，、主要功能是簽署與發佈公開金鑰憑證，撤銷某些憑 8 200818835 證與被撤銷憑證之公佈也是憑證機構責任的一部份。 非對稱式密碼系統已出現一段時間了，但是沒有如預期中的被廣 泛應用。舉例來說，使用者仍然普遍地使用通行碼(password)來登入 系統，其中並沒有涉及「公開、私密金鑰對」之使用。原因之一是確 定憑證是否正確之基礎架構是报不容易建造及運作的，而在更改私密 金鑰上的彈性不足使得這項工作變得更加複雜。因此，在此存在了一 個降低公開金鑰系統基礎架構之複雜性的需求。 在特定的環境中，一個數位訊息也許需要被數個簽署者簽章並且 僅由-低驗證者進行驗證，多重簽章技術的創造即符合此項需求。詳 見 Colin Boyd，Digital Multisignatures,，，in Cryptography and

Coding(H. J. Becker and F. C. Piper Eds.), Oxford University Press, =89, PP· 241_246。在美國專利6209091號中，描述了兩種多重簽 章系統：⑴部份簽章依序執行的乘法式多重簽章系統，與⑵不具順 序執行部份簽章的加法式多重簽章系統。這些與其他相關研究之成果 優簽章運算不再使用私密金鑰，因為數位簽章是由數個 早计异得到，而這些部份簽章則是由數位訊息與簽章子金鑰計 算^成。由私密金鑰導出簽章子金鑰後，私密金錄則不再存在。因^， 私密金鑰之私密性受到很好的保護。 八由多— 重簽章技術衍生而來，RaviGanesan等人創造了分割私密 金鑰之密碼系統(印沿_以卜3伯_1<#()17的0祚3伯1(^^詳見美國專利 N〇s.5535276,5557678,5905799等，其中私密金錄被分割為第一部 t私岔金錄與第二部份私密錄。透過此兩部份私密金錄，非對稱式 =碼系統至対兩項伽：第―，將秘密分割為兩個部份並且分別保 2可加強保護私密金錄的私密性；第二，使用者可使用—個短的秘 m但是實質上的密碼系統卻個了錄且安全之减金錄。第 個好處源於傳統上秘密保護的智慧。第二個好處有盆特殊的咅 部份職是短的RSA秘密減是可能__破密分析方絲破 200818835 解，參見 Μ·丄 Wiener 的論文：“Cryptanalysis of Short RSA Secret

Exponents, IEEE Trans. On Information Theory, May, 1990, vol. 36, no· 3, pp.553-558·” ；近來，在短的RSA私密指數上之破密分析另有 新的進展’參見 Dan Boneh and Glenn Durfee 的論文：“Cryptanalysis of RSA with Private Key d Less Than N〇292,旺E Trans· On Information Theory，July, 2000, V0|· 46, no· 4, pp· 1339-1349·”。 多重簽章與私密金鑰分割之技術增進了 RSA理論在安全性與使 用者方便性層®的價值％然而，私密金錄的變更缺乏彈性仍未被克服。 為了改變私密金鑰的各個部份，使用者仍然需要依賴下列兩種方法之 -來執订更新動作：第-，取得此兩部份私密子金麟原减金錄還 原亚且再次的分割；第二，重新產生一對「公開、私密金鑰」並且對 新的私密金錄進行切割。 —然而，將原私密金鑰回復是不太理想的，因為這個動作違反了秘 始、分剔的顧並且需要—個制的賴措叙預防回復的秘密在回復 過程中被漏；重新產生—對「公開、私密金鑰」也應被避免，這樣 會比產生初次的「公開、私密金鑰對」更為複雜，原因即在註銷被取 代的公開金鑰憑證會增加額外的成本。 因此，在私密金鑰切割技術中，需要一個更有效率與更具彈性的 方法來執行私密金餘各個部份的更新。 數位簽章可被應用於使用者鑑別上。假設在使用者端的一位使用 者向系統端要求登人，㈣端則會傳送—概數訊息當作挑戰給使用 者端，接著，使用者端會對挑戰訊息計算一個數位簽章做為回應，當 系統端驗證使用者端的回應並且驗證結果為一個正確的數位簽章，系 統端則允許使用者登入。詳細的描述可參見：“lS〇/旧C 9798_3:1998,

Information technology-Security techniques-Entity authentication —Part 3:Mechanisms using digital signature techniques·”。 這種登入方式有一個優點。假設「公開、私密金鑰對」之產生符 200818835 ，則公開麵可齡統端驗證制者端傳來_應，但 漏使！者私密金錄的私密性。如先前所提，私密金输 ί儲二p個秘㈣非由使用者所選擇的。因此，私密金鍮通常 、’例如|c卡’而經由使用者之個人識別碼 #用去^ 1取。要貫現14樣的應雜彳主f要額外的硬體成本，包括 =者的=卡與讀卡機和像是卡片之製造所 刚來’例如時間分析與錯誤分析攻擊， j用木對ic卡中的私密金鑰進行破解。 對的，目前普遍的登人過程，包括實現在Windows NT與UNIX ΓΓ/t，皆使用通行碼與對稱式密碼學。其過程可描述如下文。 =1、ΐ t 鑑別㈣庫存有合法使用者註冊的識別資料 要(二ΓΤ使用者通行碼(user-chosen passw〇rd)之赫序摘 別mS使用者端，—位使用者要求登人並且輸入他的識 的::搞ί仃：’此輸入之通行碼經過相同的赫序函數以產生-個新 統 ，、赫序之結果與以之通行碼並不會被制欲登入之系 戰使用如=’破登人之系統隨機產生—個訊息當作挑戰，用來挑 使用者π二摘要是由正確的通行碼所產生。此挑戰傳送到 用新的赫序摘要當作加密金鑰用來加密所收到 用者之應。接者’系統由鑑別資料庫中取出所宣稱的使 密之結果如與原本的挑戰相同，則視為登入^ 實复===仃碼進行使用者鏜別的方法已經被廣泛的使用，其 於柄：弋:、甬：ί缺Ϊ尚待克服。其中一個通行碼安全之威脅來自 ΐ ίί 之電腦看起來仍照往常—般正常作業，但侵入之木 纪釺;-二?' ^丁未經授權的動作，如記錄鍵盤的輸入接著將此 δ己錄傳达料面的麵。攻擊者可_木馬奴人侵之技巧竊取到機 200818835 密的資訊 子典攻擊法也顯示了通行碼的 , 中，全面性之字二= 在所已知的各種字典攻擊法 的通行碼猜測，試著針對所有使 :文=:相同 得鑑別資料庫，則全面性字典攻擊法可==二如果攻擊者可取 通行碼可被安排在攻擊者之字並中二弱通行碼’而此類 如型式，其全面性之猜測係連線進行， 對單-的i用ϋΐΐ —個閉鎖的機制去關嘗試的次數，則 面性字典攻擊有參窗、ιΑ_χ不谷易成功，但是連線的全 逐-地皆_制之防紫’因為每一個猜測被 也曰试且入所有的帳號，而非嘗試登 連線全面性字典攻擊也會癱瘓系統之服務。使用者帳號。另外， attac^r^典攻擊’被稱為加密字典攻擊(enC_〇n _〇啊 esnacK) ’ ^田述於下··一位竊舲 办 y :_禮計算所得到;因此，此攻擊者 :==: 序值作為加岔金鑰對挑戰加密，並且 w 則可判斷所猜測的PWD是否正 ;應作比較， 的。 ’ k樘子典攻擊是非常具有威脅性 個被t ’有決心的攻擊者可明發特製的登人軟體，以直接接收- 者只要取_的_2=:7利_軟體，攻擊 碼。 夂付谷易，亚不需要去破解通行 此行碼的制者認證系統仍普遍盛行於—般資Μ统中’因 此其中確實存在抵紫已知攻擊的需要，讓使用者可=安:： 12 200818835 用其熟悉慣用的通行碼系統。 【發明内容】 以非對稱式金鑰密碼學及兩份已公開的專利申請案為基礎，本專 利申請書描述了數位化使用者認證相關的範例方法、技巧、裝置及系 統等等。第一份是美國專利申請案公開號20060083370，其名稱為 「RSA with personalized secret」；第二份是美國專利申請案公開號 20060036857 ’ 其名稱為「user authentication by Nnking randomly-generated secret with personalized secret」。

本專利申明書將此兩份已公開的申請案rRSA with personalized secretjAT User authentication by linking randomly-generated secret with personalized secret」，分別稱為第一篇與帛二篇公開案。第一篇 公開案也在中華民國智財局公開，其名稱為「利用個人化秘密的RSA 密碼學方法與系統」，公開號為2〇〇629856。 「本專利申睛書中所描述到的方法與技術可能被設計於一個利用 「挑戰與回應」之程序的認證系統中，來達到使用者端與系統端之間 的安全通訊。 本申請案假設-位使用者於一部使用者工作站請求登入一部系統 ^站在此’系統工作站是—部電腦系統，且常被稱為—部系統或 2系、祕’制者工作糊是—台個人電腦，或是具有密碼學運算 田t與其他具有運算能力裝置來_的一個裝置。「系統端」與 使用者j」兩糊也在本文巾被㈣。 _某/㈣方糾用了兩個認證資料件來驗證請求登人—部電腦系 密碼金生^ _錢認料餐，是藉由一個 證資料的，絲序描述於第—篇公開案。此兩個認 個 個公 加質數作^^連的·該密碼金鎗產生程序顧了該個人化秘密與兩 作為輪入值，以產生由一個公開模數(a _icmodule)、 13 200818835 η

開指數（a public exponent)、與一個私密金鑰相關指數（a piivate-key-d印endent exponent)所組成的三元件之組合(a t|i〇)，作為 該密碼金鑰認證資料件(crypto-key authenticator)。使用者需要提供此 兩個認證資料件，才能獲得許可來登入電腦系統。 在某一貫施案中，一位使用者在請求登入一部電腦系統時，利用 -個第-輸人與-個第二輸人來產生—數位簽章，以回應來自該電腦 系統的-個挑戰。當第-輸人與第二輸人分職合使用者所持有的第 -與第二認證資料件時，則贿位簽章會是有效的；根據此推論，該 數位簽章的有效性決定了輸人賴認證龍件是否符合，同時也決 了是否授權或拒絕該登入之請求。 在本實施案巾’該電腦纽使用-把公開金絲驗證—個 的數位簽章。在個實麵巾，上述之触簽章也會在加入—個回 應訊息之使用者端進行驗證。在使聽端驗的公開全 =金錄三元件之組合中的公職數與公開指數所組成的，同^的公 開至錄也必須用於系統端。 在某案巾’使用者工作站以-個自動化的方式來取得前述 =碼錢認證龍件；換言之，該使用者工作站是被程式化:以自 個持久性記憶體巾轉該密碼金鑰三元件之組合 由 =给予明確的指示。在此實施案中，該使用者工作站更 H匕，由使用者處接收—個通行碼輸人值，作為Kim 統iii丄利用該通行碼之輸入值來產生一個數位簽章；而該電腦系 mLS，’利用—個驗證用資料來決定該數位簽章是否有效，若 i行Γ決定該通行碼之輸入符合—個事先選擇的 用的資料是-Vi門全=減請求之登人。在此實施案中，該驗證 行__金論兩者是在:冊錄的任何貝訊。而該通 14 200818835 '立使用者必須被保證系統端使用一把正確的公開金鑰來驗證數位簽 章。本專利申請案更進—步提出了—個«的方法來取代傳統上以: 個數位公開金鑰憑證_丨⑼_丨丨c_key certif丨·c_來確保公開金鑰之 真確性的方法。根據此商業方法，使用者在纽端註冊—把公開^ 並收到5主冊確5忍書(registration c〇nfjrma_。該註冊確認書說明了被 註冊之公開金錄為何，並向該使用者保證此系統端有責任使用這把八 開金錄來對數位簽章做驗證；假使有爭議產生，則該使用者可根據二 協議來指出被註冊的公開金錄為何，並據此拒絕被系統端所錯誤受 的任何不正確的數位簽章。 、又 籲。本私mt案進-魏伸了該註冊_書之械，來包含對系統 =的-項保證：若某-數位簽章的有效性可利用該註冊確認書上所圮 ，的公開金齡證實，廳使时不可以否認此數終章之有效性°。 律方法中’該註冊確認書成為使用者與系統端之間的一項法 =-實施案針對上述的商業方法進_步提供了—個補充的程序， =日:連_方絲檢查公開錢。此料向制輕證與其通訊中 '電細糸統所關公開錢與在使用者端所用者是相同的。 •的使 行碼Γ=Γ中，一位使用者選擇了一個通行碼，並使用此通 丁馬/、一個木5式認證育料件來登入網路上 個別的使用者爾料件，個別的使用 麟應到網路上_的_。在某 料f中的每一筆紀錄包含了一個密碼麵三元件=合了二 所二使用者所選擇的通行碼之間是有關連的；在 所明的弟-公瞧中描述了建立簡連的密碼錢產生程序：使用該 15 200818835 :::個別的—對質數來產生三個輸出，作為在此一集合式 枓件中的_記錄之密碼金鑰三元件德合。 、 個依ΐϋϊϊ方法巾’被聊的通行碼與該集合式認證資料件為兩 於不同的雷=因子。在系統端’使用者被允許註冊不同的公開金餘 不同=統；因此’使用者可以使用一個相同的通行碼來登入 證 數’但在_的電腦系統中使用個別的公開麵來驗 數位戏早之正確性以決定該唯—的通行碼是否被使用。 體4專33也描述了—錄件，此物件包含—個麵可讀的媒 4 /、扣7扣不一邛機态執行以下的動作··傳送一登入之 = '，·二部電腦系統；從該電腦系統接收到—個挑戰訊息；使用第一 =產腦系統傳來的ί戰訊息當作—個轉換過程的輸 至電腦^，將趙位4章與㈣者的—個朗稱呼傳送 至電細糸統，亚接收來自該電腦系統是否准許登人之 在該部電腦系統上利用相對應於使用者 匕决疋疋 金錄來驗證該數位簽章所得的―：;刪的-把挪 機哭施案中，前文依指令來執行的機器是一部個人電腦。此 I可以疋其他使时端的純或裝置，如個 D_ Assis賊PDA)，或_算及姆力的彳 從使用者的觀點來看，某些實施案之功能就如傳統的通行碼系 統，在此，存在了一個技術上的差異：在傳 由、一........ 個赫序值被儲存’以用來驗證通行碼之輸入;而根據本專:d :碼==入值來產生之數位簽章的正確性即二該 對於熟悉此技術領域的人來說，在閱讀完後文之最佳 細說明後，將可更瞭解本專辦請觸描述的目標。λ ’、 前文的-般性描述與後文的細節說明是本專利發明内容之舉例， 16 200818835 其目的為專利範圍做更進一步的解說。 _上述以及其他的範例、實施例與其變化將會在後文的附圖、細節 况明、與申請專利範圍中有更詳、細的解說。卩下藉由具體實施例配合 所附的圖式4加說明，當更容歸解本專利巾請案之目的、技術内容、 特點及其所達成之功效。 【實施方式】 /本祝明書提供本專利申請案之最佳實施例的詳細說明，同時以隨 後的圖不_各個範例實施案。文巾使關的參考編號將儘可能麵 後之圖示編號相同。 本專利申請案所描述的使用者認證是建構在一個挑戰與回應的程 f (a challenge and response process)之上，依此程序執行使用者端 =系統端的通訊。此程序是一種通訊協定(c〇_unjcati〇n pr〇t〇c〇丨）， 匕描述了一種步驟式的方式來定義兩端之間的通訊。在此程序中，使 用者端利來自-位使用者的兩個認證資料件(tw〇 authentjcat〇⑸， 來產生-個數位簽章以回應來自纽端的—個挑戰，而线端利用與 使用者相連結的一個註冊公開金鑰(a registered pub|jc吻），當作驗證 用的資料，來驗證該數位簽章之效力。 立 本專利申請案所描述的使用者認證的各種實施案中，至少有以下 的特性：第一、公開金鑰與兩個認證資料件之間有一定的關係，但公 開金鑰的揭露不會導致兩認證資料件上的秘密資訊之洩漏；第二、^ 用者可以自主性地選擇一個個人化的秘密，如使用者所選擇的通行 碼，來當作第一認證資料件；第三、使用者被允許在不改變註冊公^ 金鑰的情況下，變更該二認證資料件；第四、使用者被允許以一個: 同的秘密，如一個通行碼，當作第一認證資料件，但在不同的系统 註冊了不同的公開金输。 芩考第1圖，此圖用以說明此挑戰與回應程序的基本概念。在步 驟110中，一個使用者工作站傳送一個登入系統的請求給一部系統二 17 200818835 作站；在步驟120中，此系統工作站送出一挑戰訊息給使用者工作站， 要求使用者工作站使用兩個正確的認證資料件來準備一回應訊息丨在 步驟130中，使用者工作站接㈣代表第—認證資料件的—個第一輸 入值，以及代表第二認證資料件的-個第二輸人值，並利用此兩個輸 入值對該挑戰訊息來產生一數位簽章；在步驟14〇中，使用者工作站 用该第一輸入值來驗證該數位簽章是否有效；步驟13〇與能夠重 複執行，直到一個有效的數位簽章被產生為止；在步驟：；5()中，使用 者工作站將該被驗證為有效的數位簽章及一使用者識別（a use「 identifier)合併於一個回應訊息中；在步驟湖中，使用者工作站送出 该回應訊息給祕卫作站；在步驟17Q巾，系統工作站使用—個註冊 公開金鑰(a registered public key)作為驗證用的資料，來驗證數位簽章 的有效性，而該公開金鑰是根據該使用者識別來取得的；在步驟18〇 中，系統工作站根據步驟170的驗證結果來決定允許或拒絕其登入系 統之请求’並且通知使用者工作站其決定。 第一認證資料件是一個個人化秘密，它是使用者自主性選擇的， 如使用者所選_通行碼。第二認證倾件也麟密碼錢認證資料 件(cWto-key authenticator)，為一個公開模數(_|ic m〇du|e)、一個 公開指數（public exponent)、與一個私密金鑰相關指數 (private_key-dependent exponent)三元件的組合(trio)。 芩考第2圖，此圖用以說明本專利申請書所描述的方法之概念化 架構，類似於前述的第二公開案「藉由連結隨機產生的認證秘密與個 人化秘密的使用者認證方法」中所提到的一個架構。兩者主要的^同 在於，该專利公開案中所描述的方法，並非基於非對稱式密碼學。 第2圖以架構化的方式說明兩個基本概念，用以引導本專利申請 書所描述的設計與實施例。 第一、一對「公開、私密金鑰對」（a public/private key pair)扮演 了一個連結角色，連結了使用者端的二個認證資料件與系統端的驗證 18 200818835 ^資料。該金鑰射的公開金鑰與私密金酬_係建立了此連結。 在系統端巾’此驗證用的資料為該公開 今 =嫩該金输對具有另外的關係，而於數位簽=生= 程序中取代了該錢對。第2圖中，置於使用者端與系統端兩= 二的兀件210疋-對「公開、私密金錄對」（⑺，句，⑴，此金餘對用以 =上述描述的連結關係。在系統端的元件22〇為公開金帅句，作 25Γ=ΓΓΛ上的兩條線230及240指出該二個驗證資料件 中，在⑷金if、。在本專利申請書所描述的使用者認證系統 的計算過财出現。 鑰__•未在其後 ㈣trr者被允許在保持线端之驗射林變的情況下， 更毛、所持有的二個認證資料件。在第2圖中，該更新程序2 一個新的第一認證資料件280，以S,表 妾收 資料件250及260。 矛丁之且用以更新该二個認證 將分述的雛將於T文巾更詳細地說明，這些及其他的特性 =许我們創造-侧歧用者認證的通行瑪系統，其安全性等同於 RSA糸統，但如鱗仙者自线輕擇與 統RSA密解不製㈣缝。 &克服傳 一參考第3圖，此圖描繪了躲創造前文所定義的二個認證資料件 序^序包含了一個密瑪錢的產生程序，該程序已被 心述於弟1公開舒，它可被執行在—部使用者工作站上，如 二2 ’或是其他具有執行「似公開、私密金賴」產生程序: 運·^力的個人化裝置。該使用者工作站包含機器可讀取 備’以儲存機器可執行的指令，這些指令引導使用者工作站執行以= 的工作。步驟3彳〇 :接收一個個人化秘密305，以s表示之，此 305被視為第一認證資料件。步驟33〇 ··經由一個第 將補 人化秘密3〇5轉換成為-個暫時值332，以u表示之。步驟^該^ 19 200818835 用「RSA公開、私密金錄」產生程序，由兩個奇質數p (312)及q (314) 來產生一個公開模數n (344)、一個公開指數e (346)與一個私密金錄d (342)。步驟350 ··使用步驟330中的暫時值u (332)，與步驟34〇的 兩個奇質數p (312)及q (314)、私密金鑰d (342)於一個第二轉換式， 以產生一個私密金鑰相關指數v(355)。步驟36〇 ••從相關計算的記憶 體中刪除该私密金鑰d (342)、二個質數p(312)及q (314)，與該暫時 值U (332)。步驟370 ··由步驟340中所取得的該公開模數n (344)及 公開指數e (346)，與步驟350中所取得的該私密金錄相關指數v (355) ’、组合成密碼金餘三元件(n，e，v)(375)之組合，將此密碼金錄三 兀件(n, e，v)之組合視為第二認證資料件。步驟細：將該第二認 料件儲存於持久性記憶體385。 、 根據第3圖，該第一認證資料件不需儲存於持久性記憶體中，使 用者可自仃战’亚於f要時財動輸人。魏證資料件的雜凑值或 類似的衍生值Μ需儲存於持久性記㈣中作為驗證时料。在本專 利申請書所描述的使用者認證方法中，驗證了以第—認證資料件之輸 =所產生的-酿位簽章之核性，可「間接地」確麟輸入的正確 =。攻個娜加強了系_安全性，尤錢#第—認證 使用者所選擇的通行碼時。 阳 在第3圖的密碼金鍮三元件之組合(n，e，v)中的公開模數時公開 !曰數e組成-把公開金鑰。使用者註冊該公 作為驗證靜料，它也能夠卿m γ錄陶㉟糸統中 如第]圖中的程序所^來作為—個使咖的驗證用資料， 一個330使用了 —個第—轉換式’步驟350使用了 二轉i個轉換式可視為—對轉換式，以f1和f2表示之。 其中—^換式可以用以下的表達式表示之： f2(y，h，k，z)，LCM(h —r k—υ + ζ+((—y)咖 LcM(h —，，k 20 200818835 一1))。 在此表達式中，χ、y、h、k和Z分別表示該第一認證資料件 s(305) > u(332) ^ fp(312) > q(314)^fA^ 金錄d(342)之數值例。該—對轉換式是二個數學函數，為避免混清， f1與f2之輸入變數以新的變數符號來取代之。 在此f2的表達式中，參數c是一個非負的正整數，lcm是最小公 ^tt(LeastCommon , ^ Η iX#t(a coI!ision«resiste^^^ , 1^##^ 1

法，轉換式f1和f2的第二個表達方式為： f1(x) = H(x)，其中㈠和父如前述的定義； f2(y’ h，k’ Z) = CX(j)(hxk)+z+((—y)咖 ，其巾 c 是一個 非負的正正數，φ疋尤拉φ函數，而y、h、匕和z如同f2的第一個 表達方式之定義。 、e與11如前述之定義，而μ為一個數位訊息 假設f1、s、v 對此數位訊息Μ所作的數位簽章，可由 s丨gnature’ha’M—hash卿mod η計算之，也等同於 mGd n)x(hash(M)v咖η))咖。；在此模數卩的兩個 曰，，’ has_)_ _ η 與 hash(M)v — η，被用來計算 Μ ^ ^分触簽章。這料算二_份數錄章的工作可在單-處 ^執仃’或是在二_同合作的處職上共同執行。 2驗證-個給予的數值SGN是否是對μ所計算的一個正確的 θ早所而要的工作疋驗證haSh(MXSGN)e(modn)之同餘相等 疋舍成立。 所用ίΪΐϊ haSh(M)㈣序函數’與傳統RSA用來計算數位簽章中 1 、’、函數並無不同。相同的赫序函數也能被使用於第一轉換 式打，但這並不是作為f1所必要的條件。 如弟1圖之程序的實施例中，數位簽章在使用者 工作站上被執 21 200818835 行’该工作站可使用單個處理器或兩個處理器。 第-轉換式也必須用於使用者工作站上，而第二轉換式在創造兩 個認證資料件之後便不再使用。 如前文所描述，第二認證資料件是一個密碼金錄三元件之組合， 匕包括-個公開板數、-個公開指數與一個私密金餘相關指數。該公 開模數與私密金錄相關指數被使用於數位簽章的計算中，而公開指數 則非數位簽章之計算所需要。該公開指數被包含於認證資料件的目 的，是為了在使用者端驗證數位簽章的有效性。使用者端的驗證工作 使得系統端在遭受猜測攻擊之初即可偵測到其攻擊，因為系統端從授 響權使用者端接收到的數位簽章必然是正碟的。 現在紗照第4圖，本圖制了更新第—和第二認證資料件之程 序’此私序在使用者端執行，包含下列工作。步驟41〇 :接收一個舊 的個人化秘密402 ’以s表示之，作為第一認證資料件，並從一個持 久性記憶體409中，接收-組密碼金输三元件(n (4〇4)，e (4〇6)，v (彻》 =合’作為第二認證資料件。步驟42〇 :透過驗證測試訊息的數位 僉章之有效性來驗證所收到及所取得的驗證資料件之正確性，在此的 =試訊息可以是隨機式產生的。步驟:如果步驟的驗證結果 修為正確」則繼續下-個步驟，否則可依需要回到步驟41〇重覆不同 2輪入。步驟440 :接收一個新的個人化秘密，以s,表示之，作 田-?新的第-認證資料件，並要求使用者給予顧。步驟45〇 ··利 f第3圖的步驟330中相同的第-轉換式，來計算二個暫時的值 二=和u，，，)。步驟彻：計算v，=v_㈣)。步驟47。：用⑺，e =代弟二認證資料件(n, e，v)並且在相同的持久性記憶體中儲 值得注意的是，前述中的更新程序保持公開模數和公 文，此程序單獨在使用者端執行之。 + 在上述更新程序中出現_個缺點需要克服:在步驟獅所得到的 22 200818835 V，必須被保證是正整數Qf2的第 二表達式中的0χφ(_曰m 狀甲的CxLC_一1,卜1)和弟 的正整數c之選=，這個缺點而設計的；藉由一個適當 f1(s)之差的r斜佶4^曰㈣岔孟鑰相關指數v，可以被保證比n(s，)和 定，所謂π(ϊ，)和差證可證:根據ί1(χ)=Η(χ)之設 告Η為已知，ρ 的對值必削、於H(S’) — H⑻的絕對值， ^-個正敫數讀是個已知常數’因此’仙能選擇—個參數c i χ10Μ(ρ·Μ-υ ^ 士此所k擇的C將可保證舊 -個悝為正的結果。讀相難數V減去—個差值產生 這個變化；，』用、:2 ’此-圖說明第4圖之實施案的-個變化。在 式處理if 5G2°來執行更個主動式處理_和一個被動 是被儲存在-個建置於被“二碼金錄三元件之組合(n，e，V) 叶的目的是A了心」動式為内的—個持久性記憶體中，其設 制於被動式處理^金_指數V和它的更新值V，之資訊能被限 料件更新程序的—部份工作是要確認伽第—認證資 =件之輸入疋正確的’而在第W圖的程序中，使用一個 拽 來執行上述的確認工作將更為複雜。此二個:里 ===生之崎章的正確性，以確認該輸入之i l被動式處勤，以產生—她錄章；步驟512、5 要 別:《動式處理器接收到該要求，從持久性記憶體5〇9中: π件(Μ504)’ e _，ν(5()8))，並傳送(n，e)給主 二:ς 520、525、528和53G，主動式處理驗序執行町‘ 測試訊息Μ、計算hash(M)、傳送has_)給被動式處抑，並= 23 200818835 試訊息Μ計算DS1e hash(M)⑽m〇d n，產生—個第一部份數位簽 章DS1，步驟535,被動式處理器從主動式處理器處接收到㈣剩， 並從步驟514中接收到該公襲數n (⑽)與該私密金鑰細指數v (508)，步.驟540 ’該被動式處理器透過計算啦钟姑卿m〇d n，

產生们第—刀數位务早DS2，步驟542，該被動式處理器傳送該 第二部份婁祕簽章DS2給該主動式處理器；步驟545，該主動式處理 讀收該第-部份數位簽章DS1與第二部份數位簽章吸並計算m 的-個數位簽章：sg__SixDS2 mod n ;步驟55〇，藉由驗證 同餘相等haS_)E(SGN(M))em〇d n，來驗證該數位簽章的正確性； 频560 4步驟55〇的驗證結果是「正確的」，則該主動式處理器繼 續執行如第5_2圖從步驟57G開始的工作，若驗證結果為錯誤則 況需要回到步驟510。 第5-2圖說明密碼金錄三元件之組合⑺（5〇4)，㊀（5〇6)，v (5晴的 更新工作,。步驟57G，該主動式處理器接收—個新的個人化秘密 s’(565)，並要求使用者給予確認。步驟575，該主動式處理器利用盥 第3圖步驟330中相同的第一轉換式f1，來計算二個暫時值㈣⑻ 和u，=f1(S，）。步驟58〇，該主動式處理器計算此二個暫時值的差值， 以D表示，，即D=u，_u，並傳送給該被動式處理器。步驟哪，該被 動式處理科算v’=V-D。步驟59G，該被動式處理n獅(n，e，V，)取代 ，有的(n，e, v) ’以更新該第二認證資料件。步驟595，該主動式處理 為由被動式處理ϋ制—個通知訊息，並告知使用者更新成功。 本專利申請書制「私密金錄相關指數」這個名詞，是為了強調 此部份的密碼金鑰與私密金鑰相關，而個人化秘密則與私密金鑰無 關。固人化秘密」和「私密金鑰相關指數」共同取代「私密金鑰」， 而私後金輸則成為一個「隱藏的」秘密。 在產生與更新認證資料件的程序中，個人化秘密之選擇具有相當 的彈性’吨樣的彈性是由於f1才皮設計為一個碰撞阻抗赫序^數 24 200818835 下文中，假設個人化秘密是一個使用者所選擇的通行碼。 在註冊的程序中，使用者_第3圖所說明^序n㈣ 行碼作為第-認證資料件’並且產生-組密碼錢三元件之組合(n,e， v)作為該第二認證資料件。該使用者註冊他的識別稱呼、此模^ n’和 此公開指數e於系統工作站。 、 參考第6-1圖’此圖為實施第]圖程序的—個詳細流程說明。元 件601為-位使用者用來向-部系統工作站發出登入請求的一部使用 者工作站，元件602表示為該系統工作站。在一個網路環境中，一個 系統識別稱呼必須被絲識顺系統工作站，同樣的，—個使用者識 別稱呼也必顧來識麟使用者。倾_，該朗者工作站從^ 用者處接收-個使用者識別稱呼(605)、_個系統識別稱呼(；_個 ，行^輸人PWD_)，並且從該使用者提供的—個持久性記憶體 2取付-組密碼錢三元件之組合(n，e，v) _);步驟615，該使 用者工作站傳运—個登人之請求m紅作站，此㈣ 別稱呼所識別蚊的；步驟咖，該系統工作站產生—個挑戰 僂，息能藉由隨機方式產生；步驟625，該系統工作站 c _使时工作站；步驟咖，該使用者工作 收到呑亥挑戰訊息C ;步驟640，兮你爾| τ 乂七 C計瞀ψ _她滅立.。μ使用者工伽對所收_挑戰訊息 牛騍:^ N(C)EhaSh(C)f1(PWD)Xhash(C)V mod η ; ，献用者工作站藉由驗證同餘相等hash(C)E((SGN(c)e) 咖η來確認該數位簽章是否正確；步驟66 ^ 的，則繼續執行步驟665m π曰…主 m“果為正確 入·牛㈣叩ς — 之私序’否則視6況需要重複步驟610的輸 二’料665，雜用紅作鱗正顧 者 ::含於-個回應訊息;步_，該使用者工作== 矾息到該系統工作站·牛既如η 于、必W應 中的者系統工作站以所收到的回應訊息 斜施从乂 \冉啤作為索^，從一個認證資料庫675中搜尋取得相 μ、α已續的公開鱗，·步驟_，該系統工作站藉由驗證同 25 200818835 =等hash(C)E((SGN(C)e) mod n，來驗證該回應訊息内的數位簽 早疋否正確，其中(n，e)為該已註冊的公開金鑰，它是密碼金鑰三元件 之組合(n，e，v)(608)中的公開模數n和公開指數e ;步驟69〇，該系統 工作站根據驗證結果來授權或拒絕登入之請求並通知該使用者工作 站；步驟695，該使用者工作站接收該登人請求之決定，並依此決定 執行後續的工作。 在根據第6-1圖之流程圖的某一實施案中，該使用者工作站以自 動化的方式接收岔碼金输認證資料件，換言之，該使用者工作站被程

式化，使之從持久性記憶體中接收密碼金鑰三元件之組合，不需要使 用者給予任何的指示。此實施賴造了—個通行碼系統，它類似於傳 、調通行碼系統，就制者峨點來看，此—通行碼方法是由前文所 描述的二個認證資料件方法所演繹出來的。該通行碼方法包含了下列 步驟：當要求登入系統時，接收一個輸入作為一通行碼；使用該輸入 產生個數也簽章，使用一個公開金錄來驗證該數位簽章的正確性； 如魏位备章被驗證為正確❸，則確認該輸入符合該通行瑪，並以此 結果授權該登入之請求。 ▲第6-2圖說明了第叫圖中步驟64〇的一個變化。在此變化中， ，使用者工作站6G1使用了—個主動式處理器651及―個被動式處理 ，652來執行步，驟640 ’第6_2圖所描述的所有步驟可用來取代步驟 4〇’在此假設該三元件之組合(n，e, v) (_)被存放於該被動式處理哭 内的持久性記憶體中。步驟641，該主動式處理器計算hash(c)，其; 驟63。中所接收_挑戰訊息，隨後送出心购給該被動式 处理為，步驟642 ’該被動式處理器接收到hash(c);步驟643 動式處理ϋ郷久性記髓怖_三元件植合(n，e，v)，並傳^八 開金錄(n，e)給該絲式處理器；步驟644，該絲式處接收a e」^猎由計算DS1 _sh(c)卿D) — n產生一個第—部份數位簽 早別，步，驟645 ’該被動式處理器藉由計算DS2_sh(c)v咖门 26 200818835 產生-個第二部份數位簽章DS2，並將此計算結果傳送給主動式處理 器；步驟646 ’該主動式處理器對c計算sgn(c)eDs1xDs2 n 產生-個數位簽章，iy_執行第6_彳圖中步驟_後續的工作。第 6-1圖中的所有步驟’除步驟640外，皆在該主動式處理器上執行， 而該二個處理以上述協同合作的方式執行步驟64〇。

根據第6-1圖與6-2的實施案，—個通行碼之輸入，例如使 ^盤所鍵人的通行碼輸人，並沒有藉由通行碼的衍生值如該 的赫序值來對該通行碼輸入之正確與否進行驗證。在此實施案中，直 =驟66j才以其結果來確認—個通行碼的輸人是否符合預先選擇的 u丁碼。若步驟662之結果是錯誤的，則表示該通行碼的輸 鑰Γ資料件是錯誤的，由於密碼金鑰認證資料件並非是 由人工=輸人的，故通行碼輸人錯誤的可能性較高。 f第6·1圖所說明的範例程序中，密碼金錄認證資料

:成=低的儲存裝置中，如記憶卡、咖(_祕扭⑸Bus) J 碟或疋一個然線射頻識別標籤(RFID tag)。 來儲的被動式處理11 652包含了内建的持久性記憶體，用 而且有能力以讀算出部分的數位簽章，其中，主 的執行。在第6.2圖中的被動式處理器可能 :；^ ,〇 的鑰，必須被嚴密的保持機密，遺失」了』 處理界贫碼:大的威脅；相對的’第6_2圖中的被動式 密，因I遣^子I1金錄與私密金绩相關指數V，v僅是一半的秘 4 ^退失34—半的秘密對安全的威脅是比較低的。 报難推7 = 是與公__，然而，以公_(n，e) 是使用m t密金錄〜，在此前提之下，不論是從系統端或 而揭4 A開金錄(n，句並無助於成功地推導出v，這是前文所 27 200818835 定義的第mf2的—個結果。 在此來。仏另—半秘密的安全性，即通 ^ -t〇 .在公開金餘不變的声、7 ”斤私序中’允蜂使用者 改變了私密金：:：===碼，也 站並不需要與使用去丁於义更、仃馬的過程中，系統工作 關資訊有助於通行碼的制 < 目此线工作麵沒有得到任何相 挑戰作站利用挑戰與回應的方法來通訊。-個 臧的私後金錄」是安全的，則此通訊也會是安全的。〃要田fe ^在，用者端，通行碼之輸入並不直接以該通行碼的衍生 二’而疋間接地經由驗證該輸人產生龍位簽章之正雜，來確切每 -個通行碼之輸入的正確與否。因此，通行碼與 ^ ，。在本專利申請案中，所謂通行碼的衍生值是—個.:換：= 輸出，此轉換式以該通行碼為單一的輸入。 、

廣義的來說，私密金錄相關指數v是通行碼的—個社值。但V 是經由f2轉換式的輸綠，其中除了通行碼外，f2在轉換過程中還接 收三個輸入值p、q與d : v=f2(f1(通行碼)，p，q，d) = cxLCM(p一 —1) + d + ((-f1(通行碼)）mod LCM(p—q —υ)或 ν=_(通行 碼)，P，q，⑻+ d + ((-f1(通行碼))）m〇d _。由上述的推導過 程可知，當不知道p、q與d之值時，揭露v值仍無法得知該通行碼。 破解通行碼的其中一種方法為窮舉式的搜尋或字典攻擊，即以猜 測的方式進行攻擊。為了決定某一猜測是否正確，攻擊者必須被迫: •計算一個數位簽章並驗證該數位簽章是否正確，因此，每猜=都 28 200818835 需要？數n之下的計算，吨好 統，其猜測所需之計算比較耗時。 此傳摘 貢訊安全專家-直努力發掘細者認證的新方法， 通行碼系 其部分原因是 權的登 口為吊㈣通行碼認證枝似乎不夠安全而無法防止未 入。又因子鑑別_细or authenticati〇n)提供了 一的 利申請案所提㈣方法可以說是雙@子_的 且有專 Π鑑別方法通常使用一個使用者選擇的通行碼當 = 、’且使用生㈣徵像是指紋t作另—個鑑糊子 種型態的雙因子鑑別會違反個人的隱私。其^ physiCa, ^ Γ人ΓNumb咐為兩個鑑別因子，在這種型態的方法中，所 ，:广個完整的秘密，而真實的認證秘密如密碼學的私 疋儲存於實體的物件中。本專獅請案所描述的方法，是把私 ΖΓΓΐ作，鑑別因子，如第3圖所描述的程序，秘密的=金 ^出現㈣錄認證倾件後扣舰且在往後的計算過程中不會 •罢击文所描述的實施案，密碼金餘認證資料件被存放於-個裝 。第-認證資料件，即通行碼，則可以不被存放於任何裝 只ί使用者能夠記住即可。如_述，通行碼的赫序值或其加密值皆 =需要為了確認輸人的正確與否而存放於持久性記憶體中，而^藉由 確認該輪入所產生之數位簽章之正確與否來驗證該通行碼之輸入。曰此 種組合兩個繼㈣件_财式，是與無伽子鑑顺制有所差 回到第1 _ 6_彳中·戰與回應之程序。在此程序中，對數位 攻早，驗難錢行了喊：在制者工作站，触縣在被包含於 回應訊息之·驗證-次’ *在另—端，系統卫作站對其所接收的回 29 200818835 應訊息内之數位簽章又驗證了一次。由於這精巧的設計，系統工作站 t能經過授_登人者與未經授_侵人者，因為經過授權的 =效的數位鮮來回應挑戰。為了讓_巧的設計更有 效率’在挑I回應的程序上作以下的修改是有助益的：被包含於回 識別稱呼也一併檢查。對於此種修改有幾種可行的 、二θ σ個“纽元或—個檢查碼作為使用者綱稱呼的-H用赫序值當作驗證資訊。根據以上的設計，系統工作站 便有此力在任何線上的制攻擊開始時即發現其攻擊。 系統工_ 人疋否正確。系統端有責任確保公開 i二二公開金錄憑證是用來滿足這個需要的傳統方法，依 據坆個方法，被註_公開麵是—賴證的

Auth9my 5 ^ ί: &依賴U幾構來保職註冊公開金錄的真雜。 由於純端和憑__者朗承擔公開錢真雜之責任，所 .=、、先的CA方法可雜用者得到好處。除非系統端與共謀，否 則糸統端接制錯誤的數位簽章是會被檢 的方法髓了制者纽糾紐糾#行為轉害。 =糸統端安全控管的缺失’系統端的不當行為是有可能發生 北旦事貝上’这是已發生的資訊安全事件的主要之-。如前文之 =知識所描述的’目_通行碼認證系财存在了若干技術上的缺 j ’例如’糸統管理者或其他内部的M工可以自系統的認證資料庫中 盗取使用者識別稱啤及其相對應的赫序值，而在未經授權的情況下登 =讀用者帳號；這類未經授權的登人可用的技術包括離線的字业攻 通行特製陳體以接收通行碼的赫序值為輸人而非接收 因此，本專利中請案所說明的使用者認證方法是—種利用通行碼 30 200818835 的認證方法，但藉由CA簽證的公開金输之真確性加強了系 使用傳統㈣證機構方法來倾公鍮的真確性、王」 程度的複雜度。資訊安全專家已經明白這個複雜度的缺 申請案所提出的通行碼認證方法可簡化此—複雜程度，奴由= 分割加強工安全性所帶來的好處；遺失被保護秘密的任—半比起= 整個的秘飾引起的安全上賴慮會味少。如果 = 仍然提供相當程度的安全保護，故使用者無須立即地=二 止其么開金鑰憑證。免除了向驗機構報 ~ ==代之的則是使用者可在系統工作二= ^餘，亚m駐作站拒絕鋪的糾金賴 = 這個==出了一個商業方法，以取代憑證機構的角色， 使用者在系統工作站註冊一個公開金鑰，苴 端？的-項協議。系統工作站接受了公開金錄之註冊:二⑽: j有義務知正麵触鮮餘料正麵數位簽章1 1使用已註冊的公開麵#作是驗 f料證町數位簽 性 %，則使用者不能否認其有效性。 ^ 11 法。公開錄之合約書可作為雙方解決爭議的一個方 Hrr 在某—系統端所註冊的—把公開金錄之合約 不it開ί論驗證為不正確，則使用者有權拒絕被系統端 錯决接又之不正確的數位簽章；同樣’根據該合約書上轉文， 位簽章經合約書上的公開金输證明為正確，則使用者 有義務承涊該數位簽章之有效性。 ==書提供了-财法，以解決有·位簽章之有效性的爭 毒。心稭者&約書上的保證’使用者可以信任系統端使用正確的公開 200818835 金鑰’因而以憑證來查核公開麵之正雜便 即在曰常的商業交易行為中通常;不需要第三的慣’ 限於mi合約料商#絲可於麵難碼'魏上，不必受 8圖’賴酬了允許—位伽者撿查_把正確全 ==:::=:上被取用的-個程序。當使用者二 處νΐί, 未τ ’此檢查程序可同步執行，因此，此程 人Μ—Μ服制者信料、統端，纽可被視秘L全料冊 合约書的-翻助方法。 A /¾瑞歸 上述之公肖金銳驗妓靖赋㈣學 回應之程序,_，-部使用者工作站(8G1)從—位使== =系統識別射_)及—個賴者識職呼_);步關5，咳使 5工作站隨機產生-個訊息，並將此隨機訊息與該制者識別射 個挑戰訊息中；步驟82(3，該使用紅作站將該挑戰訊息傳 达j對應於該系統識別稱哞的一部系統工作站(802);步驟_，該系 、、充工作站使用所接文到之挑戰訊息中的使用者識別稱呼作為一個索 引’從系統端的認證資料庫(825)中檢索取得一把在系統端使用的公開 金餘；麵835，該系統工作站從該公開金錄推導出一把在系統端使 用的對稱心碼金錄；步驟840，該系統工作站以該對稱式密碼金餘 作為一把加密金鑰將該挑戰訊息中的隨機訊息加密成密文；步驟 845该系統工作站將该岔文包含於一個回應訊息中；步驟850，該系 統工作站將該回應訊息傳送給該使用者工作站；步驟852，該使用者 工作站接收到該回應訊息，並且從一個持久性記憶體中取得一把在使 32 200818835 .用者端使用的公開金錄；步驟855，該使用者工作站從在使 把在使用者端使用的對稱式密碼金鑰；二 60’该賴者工作站以使用者端使關對稱式密碼金齡為一 讀將接收到的回應訊息内之密文解密；步驟865 果二 ，則該使用者工作站決定在系統端二Ϊ 讀付二在使用者端使用的公開金鑰，並視其為正確的。 在第8圖所說明的流程圖中，步驟835使用了 —個第換 刚-把在系統端使用的對稱式密碼麵，而步驟咖職用= Γ長度之函數可作為此相;二，^ 第3圖所描述的產生兩個認證資料件之裎库，合i 性地任意選擇通行碼。即使使繼鋒# ^序允和吏用者可自主 變更已註冊的公開_。M者、、、k、，制同—的通行碼，他仍可以 更二=冊編 —把已註冊的公開金输需再次=二二開金魏是保持不變。變更 是以CA來俘罐八R八/ j用弟3圖所描述的金鑰產生程序。若 新的公開金餘憑==3=公開金錄的變更需要重新簽發 述的，註冊合約===色-同上文所描 入不同的系統工作站，㈣合、:f使用者選擇不同的通行碼來登 本專利申請案的方法，此又=者在記憶上的負擔。應用 統工作站註冊的是一 3王寸則疋〉又有必要的’因為使用者於系 碼的任何:料。開讀，祕賴金鍮並沒_關於通行 33 200818835 =文所描述，註冊合約書的方法可免除CA的需要，大幅地簡 了 &理么開金输的複雜度，如此可允許使用者註冊不同的公開金錄 的㈣工作站，或註冊―把相_公開錢於奸系統工作站 〜這樣的彈丨生來自於以下兩個理由··⑴由相對應的公開金餘來推導 私密金錄在計算上的(2)公開金齡職簡化。 蛾本專利申请案以通行碼所設計的使用者認證方法，利用了兩個認 ς因子.、⑴通行碼；（2)由公開模數、公開指數和私密金鑰相關指數三 所組成的㈣金魏證資料件㈣邮均^她⑽·⑺⑽。當使用

冊不同的Λ開金錄於眾多的系統玉作站時，其密瑪金錄認證資料 ,，们數Α之增加’乍看之下這是使用不同公開金錄的—個缺點， 「=不同的么開金餘於不同的系統工作站有一項優點：因某-把 藏的私a麵」被瓦解時，其所造成的風險可被侷限於所對應的 雜冊之系統；除此之外，下文所提供的解決方法允許使用者 擁有多把公開金鑰但可克服其缺點。 / ^擁有多數個系統卫作站的—個網路環境中，當使用者請求登入 糸二糾他必須在使用者工作站上提出所欲登入的系統之識別稱呼， 別稱呼可被當作一個索引資訊來搜尋取得與其對應的密碼 ◎'料件’換&之個密碼金錄認證資料件可以連結於一個 錢識別稱呼，而這樣的連結可被收集記錄在單一個檔案中，如此， 此檔案與通行碼兩者可視為使用者認證過程所關的輸人。此一华合 錢識別射與密碼錢認料件及其連結所形成的職，簡化了 ^過程的輸入程序，它被稱為「集合式認證資料 e authenticator) 〇 集合式認證資料件是其使用麵財的触檔案，可以被存放在 二個可攜狀m例如usb隨㈣USB stG琴deviGe)、記恨 ^emory CardHC密碼卡(丨c crypt〇咖)或是行動電話⑽丨丨 寻。使用者攜帶這樣的裝置並記住其通行碼，即可漫遊於網路上來登 34 200818835 入任何其已註冊的系統。 參考第9圖，此圖說明了一個集合式認證資料件中的所有元件。 如第9圖所示，一個集合式認證資料件是由多個個別的認證資料 件之記錄的集合。每個個別的認證資料件之記錄由下述3個項目所組 成·⑴欲登入的一部系統工作站的一個系統識別稱呼；（2)_個密碼金 錄三元件之組合；（3)此位使用者的一個識別稱呼。每個密碼金餘三元 件之組合又包含三個元件：（1)一個公開模數；（2)一個公開指數；（$ 一個私密金鑰相關指數。集合中的每一個個別的認證資料件之記錄指 出此位使用者在某一部系統工作站上註冊了他的一個使用者識別^呼 及一把公開金鑰。在此集合中，每一個使用者識別稱呼可以是唯一的 或是重複的，而公開金鑰亦然。在此圖例中，擁有此一集合式擋案的 使用者在不同的系統中分別註冊了電子郵件帳號、銀行帳號、學生學 號和身份證字號等作為他個人的使用者識別稱呼，而此集合式檔案内 的每筆個別的記錄中的系統識別稱呼識別了唯—的系統卫作站，同時 也作為一個索引貧訊，用來從此集合式檔案中，搜尋取得密碼金鑰三 元件之組合及對應的使用者識別稱呼^。 在第9圖中，編號910、92〇、93〇分別代表一個系統識別稱啤、 二個密碼金錄三元件之組合、及—個使用者識聰呼，編號_為— 筆個別的認證資料件之記錄，而編號922、似、926則分別代表一個 么開拉數、、-個公開指數、及一個私密金錄相關指數。 村其2式認證雜件是等_管_师訊與登人資料的個人用資 ;、' Μ 〃。雜f靖合約書財法，將不f要公開 ===與註冊於系統内相對應的公開金錄並沒有被、一張Μ二 欢署的ϋ連結在—起，而可以分別地予以變更。 資料i述ΓΓΓί使用者可以有彈性且簡單的管理自己的集合式認證 二入古/山允4他在—個網路環境中註冊多數個系統工作站，而且 文王又方便地登入其中的系統。 35 200818835 第10圖說明了在一個擁有多數個系統工作站的一個網路環境 中，實行使用者認證的一個實施案。此圖所描述的工作流程幾乎與第 6-1圖的工作流程相同，其差別在於：第1〇圖中使用了 一個集合式認 證資料件(1008)，而第6-1圖則是使用了 一個單一的密碼金鑰認證資 料件(608)。第10圖的實施細節將於下文描述。 、 元件1001為一位使用者用來登入系統的一部使用者工作站，元件 1002則是該使用者欲登入的一部系統工作站。步驟1〇1〇，該使用者 工作站從該使用者處接收到一個使用者識別稱呼(1005)、一個系統識 別稱呼(1007)、以及一個通行碼的輸入PWD(1〇〇3)，並進一步由使 用者所提供的儲存設備中接收一個集合式認證資料件(1〇〇8);步驟 1012，該使用者工作站利用該系統識別稱呼作為一個索引資訊，從集 合式認證資料件中搜尋取得相對應的密碼金鑰三元件之組合；步驟 1015，該使用者工作站向經由該系統識別稱呼決定的系統工作站發出 登入之請求；步驟1020，該系統工作站產生一挑戰訊息c，該挑戰訊 息C能夠以隨機方式產生；步驟1〇25，該系統工作站傳送該挑戰訊息 C到該使用者工作站；步驟1〇4〇，該使用者工作站接收到該挑戰訊息 C，並對所收到的訊息C計算出一數位簽章，計算公式如下：sgn(C)

Ehash(C)f1(PWD)xhash(C)v mod η ;步驟 1060，該使用者工作站藉由 驗證同餘相等hash(C)E((SGN(C)e) mod η，來驗證該數位簽章是否 有效；步驟1062 ’若驗證結果是有效的，則繼續執行步驟1〇65，否 則視情況需要重複回到步驟1010 ;步驟1〇65，該使用者工作站將該 有效的數位簽章及該使用者識別稱哞(1〇〇5)包含於一個回應訊息中； 步驟1G7G，該使时工作站傳送該回應訊息到該系統工作站；步驟 1080，该系統工作站以接收到之回應訊息中的該使用者識別稱呼作為 一個索引資訊，從一個認證資料庫1075中搜尋取得一把已註冊的公開 金鑰；步驟1085，該系統工作站藉由驗證同餘相等hash(c)E ((SGN(C)e) mod η，來驗證該回應訊息中的數位簽章是否有效，其中 36 200818835 (n，e)是該已註冊的公開金錄；步驟1〇9〇，該系統工作站根據驗證的 結果授權或拒絕該登入之請求，並將此決定通知該使用者工作站；步 驟1095，該使用者工作站接收到該登入請求之結果，並據此執行後續 耘序。在此貫施案，步驟1〇8〇中該系統工作站所獲得之已註冊的公開 金鑰，與步驟1012中該使用者工作站所取得的密碼金鑰三元件之組合 (n，e，v)中的公開模數n與公開指數e所組成的公開金鑰相同。 在第10圖所描述的流程所獲得的另一個實施案中，該集合式認證 資料件可以用自動化的方式供使用者工作站存取，換言之，使用者工 作站不需要來自㈣者明柄指示便可轉侧的認證資料件之記 錄、。-般的使用者可能無法區分此—實施案與—般傳統通行碼系統間

的差別，豸而，如同前文所詳細說明的，在技術上確實有相當程度: 差異。 又J 對於熟悉此技觸_人來說，做ά不背離本專财請案之 =或精神的各項修改或變化是可能的，這類的修改或變化將被ς為 =辦請案的—雜’只要其修改或變轉同於本專辦請案中之 r所述之實施例’僅為本專利申請書中所描述_方法鱼技 施例而已’並非时限定本專辦請案所能實施之範圍 圍所述之形狀、構造、特徵及精神所為之 勺等夂化或修飾，均應包括於本中請案之中請專利範圍内。 ； 【圖式簡單說明】 制=件中的附圖是為了提供對本專利申請案更進一步的

FlI讲於本專利申請案中，作為其—部分。在附圖中：、曰 ^ t述了本專辦輪刪的「挑戰與回應」之程序，作為你 用如而與錢端之_通訊轉，在此 :為使 證；口子^求且人起統端，而系統端使用—把公開麵來驗 37 200818835 第2圖是-個觀念性的架構圖，說明了一對「公開、私 __她key _的連結角色，連結使用者端的二個認證因二， 系統端的-個驗證用資料’且進-步說明了—個更新程序，# 序允許使用者在保持祕端之驗翔資料不變的情 ’、王 有的二個認證因子； 文辦其所持 第3圖描述了產生第彳_第2圖巾所賴二個認證因子 程序來自前文所謂的第一公開案； 斤’此 第4圖描述了-個更新程序’以更新第3圖之程序所產生的兩個外登 因子，此程序同樣來自前文所謂的第一公開案；

第5-1 ®與第5-2圖描述了第4圖所述更新程序的一個變化· 第6-1圖是-個流程圖，描述了第】圖中所述「挑戰與」 的實施案範例； ^ $斤 第6-2圖是-個流糊，描述了在第μ射#使用者工作站使用一 ^固主動式處理器與-個被動式處理器時，纟中的—個特定步驟之變化； 第7圖心述了彳b使用者公開金錄合約書的範例，表達了使用者與某 -系統端對公開麵朗上之協議，其目的是實現—個商業方糾取 代傳統上使用的公開金鑰憑證(pub丨丨c_key certjfjcate); 第8 BU田述了個公開金錄連線檢查程序，為第7圖中公開金錄合約 書之商業方法的一種補強方法； 第9圖彳田述了术合式4證資料件之範例及其組成之元件，用於在一個 擁有多個系統的網路環境中之使用者認證； 第10圖描述了-個範例實施案，此實施案棚了第9圖之隼合式認證 資料件。 【主要元件符號說明】 38 200818835 一 110步驟 120步驟 130步驟 140步驟 150步驟 160步驟 170步驟 180步驟 210公開、私密金鑰對 • 220公開金鑰 230表達元件之關聯性的連結 線 240表達元件之關聯性的連結 線 250第一認證資料件，即個人化 秘密，以符號s表示之 260第二認證資料件，即密碼金 錄認證貧料件 Φ 270更新程序 280新的第一認證資料件，以符 號s’表示之 300第二認證資料件產生程序 305個人化秘密，以符號s表示 之 310步驟 312質數p 314質數q 330步驟 332暫時值，以符號u表示之 340產生RSA公開、私密金鑰 對的計算程序 342私密金鑰，以符號d表示之 344公開模數，以符號η表示之 346公開指數，以符號e表示之 350步驟 355私密金鑰相關指數，以符號 v表示之 360步驟 370步驟 375密碼金鑰三元件之組合，視 為弟二認證貢料件 380步驟 385持久性記憶體 402個人化秘密，以符號s表示 之 404公開模數，以符號η表示之 406公開指數，以符號e表示之 408私密金鑰相關指數，以符號 v表示之 409持久性記憶體 410步驟 420步驟 430確認被驗證的數位簽章是 否有效 39 200818835 ， 440步驟 445新的個人化秘密，以符號s’ 表示之 450步驟 460步驟 470步驟 501處理器執行的工作 502處理器執行的工作 503個人化秘密，以符號s表示 • 之 504公開模數，以符號η表示之 506公開指數，以符號e表示之 508私密金鑰相關指數，以符號 v表示之 509存有密碼金鑰三元件之組 合的持久性記憶體 510步驟 512步驟 _ 514步驟 516步驟 520步驟 525步驟 528步驟 530步驟 535步驟 540步驟 542步驟 545步驟 550步驟 560確認被驗證的數位簽章是 否有效 565新的個人化秘密，以符號s’ 表不之 570步驟 575步驟 580步驟 585步驟 590步驟 595步驟 601使用者工作站執行的工作 602系統工作站執行的工作 603通行碼之輸入，以符號 PWD表示之 605使用者識別稱呼 607系統識別稱呼 608存有密碼金鑰三元件之組 合的持久性記憶體 610步驟 615步驟 620步驟 625步驟 630步驟 640步驟 641步驟 40 200818835

642步驟 643步驟 644步驟 645步驟 646步驟 651處理器執行的工作 652處理器執行的工作 660步驟 662確認被驗證的數仅龙土 η 否有效 双早是 665步驟 670步驟 675使用者認證資料庫 680步驟 685步驟 690步驟 695步驟 8〇1使用者X作站執行的工作 802系統工作站執行的工作 8〇3系統識別稱呼 804使用者識別稱呼 810步驟 815步驟 820步驟 825使用者認證資料庫 830步驟 835步驟 840步驟 845步驟 850步驟 852步驟 855步驟 860步驟 865步驟 900集合式認證資料件 910系統識別稱呼 920密碼金錄三元件之組合 922公開模數，以符號η表示之 924公開指數公開指數’以符號 e表示之 926私密金鑰相關指數，以符號 v表不之 930使用者識別稱呼 940集合式認證資料件中的一 筆記錄，此記錄包含一個系 統識別稱吟、一個密碼金錄 三元件之組合、及一個使用 者識別稱呼。 1001使用者工作站執行的工作 1002系統工作站執行的工作 1003通行碼之輪入，以符號 PWD表示之 1005使用者識別稱呼 1007系統識別稱呼 41 200818835 ’ 1008存有集合式認證貧料件的 儲存設備 1010步驟 1012步驟 1015步驟 1020步驟 1025步驟 1040步驟 1060步驟 φ 1062確認被驗證的數位簽章是 否有效 1065步驟 1070步驟 1075使用者認證資料庫 1080步驟 1085步驟 1090步驟 1095步驟 ⑩ 42

Claims (1)

1. 200818835 十、申請專利範圍： 1_ 一種以非對稱式岔碼學為基礎的使用者認證方法，包含： -位使用者請求登人-部電腦系統時，提供—個第輸入鱼一 個第二輸入； /、 當所提供的第-輸人與-個個人化秘密符合，且所提供的第二 輪入與-個密碼金錄認證資料件符合時，授權此位使用者登入此^ 腦系統，在此的密碼金錄認證資料件包含一個公開模數、一個 指數、一個與私密金鑰相關的指數；以及 在沒有變更此公開模數與此公職數崎況下，變更原個人化 秘密為一個新的秘密且更新私密金鑰相關指數。 =請專讎ffi第1撕述財法巾，其個人触 用者所選擇的通行碼。 j 1 如申請專利範圍第1項所述的方法’進一步包含： 利用該個人化姆和兩個奇·在—摊 1生該糾錄、公戦.數、與私密錢細触^生的私序的°4=1:所述的方法中，更進-步的使一 ^綱，第4項所述的方法中，挑戰與_的嫩_喻_統端傳來包含在使__ —種以非對稱式密碼學為基礎的使翁認證方法，包人. ί要未登人系統時，接收—個輸人當作-個通行碼. 使用該輸入產生一個數位簽章； 馬， 使用-把公開金輪來驗證該數位簽章；以及依據數位嫩㈣崎爾，从否符合該 2. 3. 4. 5. 6. 43 200818835 通行碼，並依此結果授權登入。 8.如申料概圍第7摘義方法巾，進—步包含在_該 鑰不變的情況下，變更該通行碼。 汗i 9·如申請專利範圍第7項所述的方法中，進一步包含： 使用該通行碼和兩個質數在一個密碼金输產生的程序中 该公開金錄與一個私密金输相關指數；以及 使用該輸人值_减錢侧減來產生練位簽章。 1〇·-種財對献麵學絲礎的制者織方法，包含：

   藉由驗證數位簽章來允許登入的要求；以及 驗證為 使用一份註冊合約書上的一把公開金鑰來推翻被錯誤 有效的一個數位簽章之效力。 、 11.如專利範㈣1G項所賴方法巾，進—步包含使用該註冊合 約曰上的該公開金錄，以解決有關數位簽章之有效性的爭 Q 2.如申請專纖㈣賴方法巾，進-步包含檢查—把正癌 的公開金毅何以在—㈣腦L作站上餘用的程序。 •如申凊專利範圍第12項所述的公開金鑰檢查程序包含： •在-台使用者工作站，傳送-個隨機訊息給該電腦系統工作 站， /在該電腦系統工作站，由一把系統端的公開金錄來推導 糸統端的對稱式密碼金錄； ^該電_統工㈣，該线端崎稱式純金输當作一 把加密金鑰，來加密該隨機訊息以得到一密文； ""田 在該電腦系統工作站，將該密文傳送給該使用者工作站· 在該使用者工作站，由一把使用者端秘開金錄推導出一把使 用者端的對稱式密碼金鑰； 在該使用者工作站，使用該使用者端的對稱式密瑪祕 把解密金鑰，將該密文解密；以及 田 44 200818835 14. 一 /在献用者工作站，當其解密結果符合原隨機訊息時，決定該 糸統知的公開金合該錢的糾錢，也因歧正柄。 種應用於擁有多部電腦系統的網路中，以非對稱式密碼學為基礎 的使用者認證方法，包含： 允許-位制者制-個通行碼在網路上登人不同的電腦系 統； 允=路上的每-部電職統，_其_的—把公開金錄來 作數位食章之驗證，以決定該通行碼是否被使用；以及

   當通行碼被驗證為被使用時，允八 15. 如申請專利範圍第14項所述的方法^二步的允許使用者在不 改變公開金鑰的情況下，改變其通行碼。 16. 如申請專利範圍第15項所述的方法中，進一步包含： 使用該通行碼，並分別使用一對質數，在一個密碼金餘產生的 程序中’為每一部電腦系統，產生其個別的該把公開金錄，並產生 相對應的一個私密金鑰相關指數； 使用該通行碼和相對應的私密金鑰相關指數來產生一個數位 簽章；以及 使用與其對應的公開金錄來驗證此數值簽章，以允許登入。 17·-個物件，此物件包含—個機器可讀的舰設備，儲存機器可執行 的相W曰々’用於根據非對稱式密碼學為基礎的使用者認證，其指 令引導一部機器執行以下的動作： 使用第輸入、第一輸入與一部電腦系統傳來的挑戰訊息當作 一個轉換過程的輸入，來產生一個數位簽章； 傳送該數位簽章到該部電腦系統；以及 接收一個請求登入的決定，此決定可能是被允許登入或拒絕登 入，匕疋在該部電腦系統上驗證該數位簽章所得的一個結果。 18·如申请專利範圍第17項所述的物件中，其指令進一步使該機器驗 45 200818835 證該數位好，然後再傳送給該部電腦系統。 套=於使用者涊證的禮碼學系統(aqptosy细叫，包含· 法當提出-個登入系統的請求時，接收一個輸入當作通行瑪的方 使用該輪入產生數位簽章的方法； 使，-把公開金錄來驗證該數位簽章的方法；以及 、決定此輪入符合通行碼並依據此結果授權此登入之浐 法，在此之決定是根據驗證該數位簽章是否為正確二。、 保知不、交的情況下，改變通行碼。 21·如申請專利範圍第19項所述的系統中，進—步包含： 使用該通行碼和兩㈣數在—個密碼金财生程序中 把么開金錄與-個私密金錄相關指數的方法；以及以 使用該輸入與該私密金錄相關指數來產生該數位簽章的方法。

   46