第一章 認識電腦門神-通行碼確認系統

電腦門神 指紋 筆跡 聲音 磁卡 通行碼

通行碼的屬性 1、 組織 2、 長度 3、 壽命 4、 源起 5、 主權 6、 分配 7、 儲藏 8、 載入 9、 傳遞 10、鑑認時段

通行碼之長相 （1）輔助罩式 （2）選擇式 G ＝ “LOVE” 使用者： L O V E M= “001001000101” 隨機式 日期式 時間式 表列式 ：附加隨機字元 （2）選擇式 系 統： “KNVZALOBMA” 使用者： “VZOB” “0011001100” 鏡射罩選取式： “BOZV” 後續字元罩選取式： “WAPC” 系 統:”K5LS3R4VN1SI2Z” “0123456789” 使用者： “LRVSZ” 起始字元選取式 系 統： “K5TS3R4VN1Z” “0123456789” 使用者： “ZRVT” 上升下降起始字元選取式

通行碼之長相(續) （3）選擇式 （4）問答式 系 統： “538929” （a1＋a2＋a3＋a4）a5 a6 使用者： “486” 系 統： “538929” （a1＋a2＋a3＋a4）a5 a6 使用者： “486” （4）問答式 系 統：桌子 使用者：小鳥 系 統：頭髮 使用者：花 系 統：指甲 使用者：燈泡 系 統：手 使用者：水 系 統：鉛筆 使用者：電話

通行碼之長相(續) （5）密語式 （6）時間區段式 “taiwanisabeautifulisland” “dtaiwanisabeautifulislan” 組曲式： 使用者：“42212” （33127，45936，56713，66525） 使用者：“56713” 系統：OK! 使用者：“82712” 串列式： 82712 （6）時間區段式 9：00 使用者：“ABEDF” 10：00 使用者：“EIGHB” 11：00

通行碼注意 長度適宜，沒有意義 記事簿 不同電腦用不同通行碼 不宜活太久 不存檔 守口如瓶 ×

通行碼確認系統 （1）傳統式 ID 格式是否正確 1 2 . n 否！拒絕 IDi 是 通行碼表 ID1 ID2 . IDn PW1 PWn 使用者名稱 通行碼 PWi 1 2 . n ID1 ID2 . IDn 通行碼表 取出 否！拒絕通關 比較 PWi = i ? 是！接受通關 IDr r 缺點：亂加

通行碼確認系統（續） （2）單程函數式 ID 格式是否正確 1 2 . n 否！拒絕 IDi 使用者名稱 通行碼密文 是 PWi F(PW1) F(PW2) . F(PWn) 通行碼表 F 取出 通行碼表 否！拒絕通關 F(PWi) 比較 F(PWi) = i ? 是！接受通關

通行碼確認系統（續） （3）試驗圖樣式 ID 格式是否正確 否！拒絕 IDi PWi 是 其中 計算 KAi=DMK(PWi) 驗證表 . IDn TP1 TP2 TPn 計算 KAi=DMK(PWi) 驗證表 TPi 計算 取出IDi 計算 F(IDi) 否！拒絕通關 比較 VPi = F(IDi) ? 缺點：1. MK 要保密到家 2.PWi要交給系統管理者 是！接受通關

通行碼確認系統（續） （4）公開金匙式 ID 格式是否正確 否！拒絕 IDi 產生試驗圖樣 是 PWi IDi PWi=SKUi TPi . IDn TP1 TP2 TPn TPi EPKS PKS DSKU EPKS VPi EPKU PKUi EPKS DSKS SKS VPi = EPKS(IDi) ? 否！拒絕通關 TPi 是！接受通關

通行碼確認系統（續） （5）二次同餘式 定義 例子 假如 gcd(a，n)＝1且可以找出一個整數x，使得x2＝a (mod n)， 則稱整數a為一個QR mod n；否則a稱之為一個NQR mod n。 例子 N=11，則5為一個QR，因為42 mod 11 =5。而6為一個NQR， 理由是在[1，10]之間找不到任何一個整數x，使得x2 mod 11≡6。

QR mod n之數的性質 (1)令n為一個大於2的質數，且0< a< n，則 若a為一個QR； 其他。 (2) 若n= p×q，其中p與q均為整數，則有四種可能性 (a) a為p之QR，亦為q之QR。 (b) a為p之QR，但為q之NQR。 (c )a為p之NQR，但為q之QR。 (d)a為p之NQR，且為q之NQR。 (3) QR×QR＝QR； NQR×NQR＝QR； QR×NQR＝NQR。 (4)令p為一個大於2的質數，則它的QR共有 個，它們分別是： 12，22，32，…，( )2 mod p。 (5) 若a同時為p與q之QR，則a=x2 mod n有四組解， 其中n=p×q。

二次同餘數式通行碼確認系統 選取兩個大質數p與q並且滿足4｜(p+1)且4|(q+1)；令p與q各為100位數。 計算n=p×q。 由性質(4)計算p與q之QR與NQR之集合。 令SQR-p={12，22，…，( )2 mod p} ， SNQR-p={a|0<a<p且a為整數}- SQR-p， SQR-q={12，22，…，( )2 mod q} ， SNQR-q={a|0<a<q且a為整數}- SQR-q 。 (4) 令αSQR-p∩SQR-q，β  SQR-p∩SNQR-q ，  SNQR-p∩SQR-q，γ  SNQR-p∩SNQR-q 。 (5) 任選一個使用者的ID，由性質(2)知：此ID有四種可能性。 (6) 若此時ID不同時為p且為q之QR，則可以利用QR mod n之數的性質(3)，從α，β，  ，λ四個數中找出一個參數，與之相乘。 (7) 得到修正後的ID為p與q之QR，亦即ID = r × ID。 從性質(5)得知ID=PW2 mod n一定有解。

利用(ik, jk)從修正表中找尋所對應的參數值r 否！拒絕通關 IDk ID 格式是否正確 PWk 是 驗證表 (i1, j1) (i2, j2) . (in, jn) ID1 ID2 . IDn 計算 IDk=PW2k mod n 從驗證表中，找尋對應的參數值r … 取出(ik, jk) 修正表(存在ROM中) (i, j) 參數值(r) 利用(ik, jk)從修正表中找尋所對應的參數值r (0, 0) (0, 1) (1, 0) (1, 1) α β  λ … 計算IDk= r × IDk 比較是否IDk ≡IDk? 否！拒絕通關 是！接受通關

例子 (1) 令p=7且q=11，滿足4|p+1且4|q+1。計算n=p×q=7×11=77。注意：此時系統可以公開n，但p與q必須保留。 (2) 從SQR-p={1,2,4}，SNQR-p={3,5,6}，SQR-q={1,3,4,5,9}，與SNQR-q={2,6,7,8,10}中，找出α=4，β=2，=5且λ=6。令ID1=3，ID2＝2與ID3＝6分別為三位使用者的識別號。由於ID1 SNQR-p∩SQR-q，ID2 SQR-p∩SNQR-q ，且ID3 SNQR-p∩SNQR-q ，為使所有使用者識別號均同時為p與q之QR，因此需作如下的修正，即ID1=ID1=3×5=15,ID2=ID2 β =2×2=4，ID3=ID3 λ =6×6=36。分別算出PW1＝64，PW2＝9，PW3＝71。 (3) 當使用者鍵入ID1＝3時，系統及從ROM中讀出=5與之相乘而得到ID＝15；接著使用者鍵入PW1＝64，系統即計算ID1 ＝PW2 mod n =642 mod 77=15，由於ID1＝ID1，因此系統准許使用者通關。

破解「二次同餘數式通行碼確認系統」 Registration Phase 1. Each user submits his identity ID to the system. 2. System chooses a proper parameter r{, , , }, and computes as modified ID as ID=r*ID such that ID  QRp  QRq. 3. System computes the corresponding password PW as ID=PW2 mod n.

How to compute the corresponding PW for ID=3 without knowing p and q? 1. PW and ID should satisfy one of the following equations 2. There is one element in {*ID, *ID, *ID, *ID}, which is in QRp and QRq. → There is one element in {*ID, *ID, *ID, *ID}, which is in QRp and QRq.

3. An intruder successively submits four identification numbers 4. An intruder can get the corresponding passwords where r1, r2, r3, and r4 are in {, , , } such that

Since one of is in QRp and QRq 5. Since one of is in QRp and QRq there is one ri in {r1, r2, r3,r4} equals to  that is, one of the following expressions holds:

PW can be one of the elements in

Using a Mouse As the Login Device for Visual Cryptography Oriented Password Authentication Scheme

Login Phase - Example The Password is incorrect

Login Phase - Example The user successfully login to the system, if he clicks the correct random Arabic numerals

Registration Phase ID & Password Generate the pseudo ID image by ID & Password Store the pseudo ID image into the memory card Memory card Example of pseudo ID image

Login Phase - System Generate the ID image by the received ID Randomly generate a verification vector. Ex: 0321 Construct the corresponding verification image Send the verification image to the terminal ID image verification image  =

Login Phase - Terminal Read the pseudo ID image from the memory card Construct the ID image by the pseudo ID image and user’s Password Display the stacked result by the ID image and the verification image Correct Password Incorrect Password

Login Phase The user clicks the Arabic numerals (verification vector) which are shown in the terminal. The system accepts the login request if the verification vector is correct.

Basic Counterfeit Stacked

Basic Counterfeit Stacked ＋ ＝

Conclusions User can select (ID, PW) freely System does not maintain PW file No complex computations Messages transmitted are efficient Can withstand replay attack