Digital Signature Forged in USA Integrity Authenticity Unforgeability Non-repudiation Irreusability Forged in USA

common senses Conventional signature VS. Digital signature A signature is physically part of the document being signed. A digital signature is not attached physically to the message that is signed. A signature is verified by comparing it to authentic signatures. Digital signatures can be verified using a publicly known verification algorithm. A copy of a signed paper document can usually be distinguished from an original. A “copy” of a signed digital message is identical to the original. common senses

Digital Signatures based on DLP: ElGamal signature scheme Schnorr signature scheme Digital Signature Algorithm (DSA) He and Kiesler’s signature scheme

Digital Signatures based on FAC( factoring problem): RSA signature scheme Rabin digital signature scheme OSS( Ong, Schnorr, & Shamir) signature scheme Modified OSS signature scheme

TTP TTP被完全信任? 3. C’ 2. C 1. C=Eka(M) 傳統(對稱性)加密法之數位簽章需可信賴之第三者之助方得竟其功.{參考下圖} M=Dka(C) C’=Ekb(M) TTP 3. C’ 2. C 1. C=Eka(M) M=Dkb(C’) Alice 與 Bob 沒有約定session key,兩人與 TTP 分別約定 session keys ka 及 kb, Bob 收到密文后直接轉給 TTP,而 TTP 用與 Alice 約定之session key 解得明文,再用與Bob約定之 session key 加密后,送給Bob. TTP被完全信任?

RSA數位簽章 Alice Bob Alice 送出 C = (MdA mod mA)eB mod mB 簽章 加密 1. 本法乃為了確定送方身份而存在. 2. 所謂簽章,就RSA而言只不過送方先用唯獨自己知道的私鑰(private key) 加一次密之謂. Alice Bob Alice 送出 C = (MdA mod mA)eB mod mB 簽章 加密 Bob 解得 M = (CdB mod mB)eA mod mA

Probabilistic encryption systems: 機率式公開金匙加密系統: PKC中，如Knapsack，RSA，ElGamal等均 是確定式的(明密文一對一固定方式)，所以Intruder可以從截收到的密文C=E(M)中，針對數個最有可能的明文，如M’，進行加密而得C’=E(M’)。然後再將C與C’比對，若C=C’ 則可知M=M’。質言之,確定式的保密系統對Intruder而言，其破密資訊是可以累積的。 機率式加密系統對每一個明文使用不同的亂數(當然是在加密時)，因此一個明文可以對應到很多不同的密文。而解密時卻是解得唯一的明文。 Rabin Public Key cryptosystem(1979) Rabin的方法是一個密文C可以對應到四個明文M(之中只有一個是正確的)。因此，在加密時必須加入一些有意義且易於分辨的訊息於明文中，使得解密時能夠明確地還原出原來的明文(參見次頁) 。

方法簡介: 選定n=p*q; 其中p與q是大質數。令明文為M，密文為C，公開加密金匙為 (b,n)，秘密解密金匙為(p,q)。 [加密程序]: C = M * (M + b) mod n， 其中b是亂數。 [解密程序]: 根據上式可知M2 + M*b - C = 0 mod n. 故明文可由下述四者之一算出: M = -b/2 (b/2)2+C mod p M = -b/2 (b/2)2+C mod q

ElGamal 數位簽章 系統已知 簽署作業 驗證 [ 此法之簽體(即明文 M)不能似 RSA簽章法之可直接還原] 大質數 P, mod P 之原根g , 簽署者 B 任選之整數(私鑰) x , 1<x<P-1 B 算出之公鑰 y = g x mod P {用原根g 以免被解 離散對數} 系統已知 簽署作業 [ 此法之簽體(即明文 M)不能似 RSA簽章法之可直接還原] 對明文M, 1MP-1, B選一整數 k, gcd(k, P-1) = 1, B 計算簽署文 (r, s)滿足 : r = g k mod P, s = k -1 (M - x r) mod P-1(或 M = x r + k s mod P-1). B 將 (r, s)送給 A. 驗證 驗證者 A verifies 下式是否為真 ? g M = yr r s mod P  gM = gx r g k s = yr r s mod P

安全性分析 { M1 = x r + k s1 mod P-1 M2 = x r + k s2 mod P-1 而求解 x 與 k 易矣 ! 1. 若可由 y = g x mod P 中之 y 及 g 推算出 x ,則本法危矣! (Discrete Logarithm Problem.) 2. Intruder A’ 欲偽造 (r, s) 以滿足 g M = yr r s mod P 同樣面臨解 DLP. 3. Intruder A’ 若獲得明文 M 及其簽署 (r , s), 則因為 M = x r + k s mod P-1, 可知 想算出 x 及 k 兩未知數難矣. 但若 B 利用相同的 k 簽署 M1 與 M2 而得 簽署文 (r , s1) 及 (r , s2)  r = gk mod P, 則 聯立 M1 = x r + k s1 mod P-1 M2 = x r + k s2 mod P-1 而求解 x 與 k 易矣 ! 4.intruder 可偽造 M 之合法簽署 (r, s) ;此intruder 偽造簽署文 (r, s) 如下: intruder 任選兩亂數 u and w, 1 < u, w < P-1 and gcd(w, P-1)=1, 計算 r = g u y -w mod P ………(1) s = r w -1 mod P-1 ………(2) 及 M = u s mod P-1 ………(3) {注意: M無法由intruder事先自定,它是被算出的因變數} 得 yr r s = yr (gu y -w)s = yr gus y -ws = yr gus y -r = gus = gM mod P. 但明文M 無法由intruder事先自定;即M可能是無意義的數字爾 ! 故此種偽簽嚴格來看是nonsense. 不過所有DS均有此攻擊法,而解決之道即引進單向赫序函數 ! {

For a (finite) multiplicative group G, define the order of an element gG to be the smallest positive integer T such that gT = 1 = g0 in Zp. 若 gG 之 order 是 P-1 {P為質數且集合 G 定義於ZP}, 則 g 稱為 mod P 之原根. //當 g 為 mod P 之primitive root, 由 g 所產生之序列(sequence) 具有最大週期, 因此安全上較佳.// 理論上可證: 對所有質數 P, 其原根必定 存在. 若 g 為 mod P 之 primitive root, 且 a 與 P-1 互質, 則 g a mod P 必為 mod P之原根. mod P 之原根個數等於 (P-1) ---------- Euler Totient Function. 例: 若 p=10, 則 (10)={1,3,7,9}, 因此 p=11 時共有 4 個原根; 即 [ 因我們已知 2 是 mod 11 之原根, 故] 21 = 2 23 = 8 27 = 7 29 = 6 2, 8, 7, 6 均是 mod 11 之原根

多數數位簽章法均有類似的攻擊法存在,若能使用 one-way hash function 合併之,則可高枕無憂矣. 請參照後續之介紹. Why One-way: (1) hash fun 對任意長度的明文,產生固定長度的密文. (2) hash fun對任意明文M, 藉 HW/SW 易求得 h(M). 防攻擊 : (3) 對任意hash fun 值 x, 計算上不可能藉 x=h(M)求M. (4) 對任一明文M1,要找另一明文 M2 使得 h(M1 ) =h(M2) 在計算上不可行. (5) 要找任一對 (M1 ,M2)明文對,使得h(M1 ) =h(M2)  Unfortunately, although there are many functions that are believed to be one-way, there currently do not exist functions that can be proved to be one-way.  Zm is defined to be the set {0, 1, . . . , m-1}, equipped with two operators, + and *. Addition and multiplication in Zm work exactly like real addition and multiplication, except that the results are reduced modulo m.  相信 f(x) = xb mod n, gcd(x, n)=1 是 one-way function.  For a (finite) multiplicative group G, define the order of an element gG to be the smallest positive integer t such that gt = 1 in Zp.

Digital Signature Algorithm (DSA) 1991年，美國National Institute of Standards and Technology (NIST)公佈DSA為國家數位簽章標準(DSS)。DSA公佈後，引發以下幾點重大爭議(原則上，業界及學界仍是接受此一標準)： (1) DSA不能用來做加密或金鑰分配之用，只能用來做數位簽章。 (2) DSA是由美國國家安全局(NSA)所發展出來的，不像RSA或 ElGamal數位簽章法是由學界人士所設計出來的，普遍上仍是存在 是否存有暗門(trapdoor)的疑慮。 (3) DSA的計算速度比RSA要來得慢。簽署時間與RSA大約相同，但 驗證簽章的時間要比RSA慢上約10至40倍。 (4) RSA雖然不是政府頒布的一項標準(牽涉到專利的問題)，但是全世 界的使用者早已將之視為一項重要的數位簽章標準來使用。

我國電子簽章法 我國電子簽章法 於民國九十一年四月一日正式實施. 其立法依循 (1)技術中立 (2)契約自由, 及(3)市場導向 三原則為之. (1)技術中立 : 任何可以確保資料在傳輸或儲存過程中之完整性、可以鑑別使用者身分之技術,皆可用來製作電子簽章,並不以“數位簽章”為限. (2)契約自由 : 對於民間之電子交易行為,宜在契約自由之原則下,由交易雙方自行約定使用何種適當的安全技術、程序及方法製作電子文件及電子簽章. (3)市場導向 : 指政府對於憑證機構管理及電子認證市場發展,採取最低度的必要規範,電子認證機制之建立及電子認證市場之發展,宜由民間主導發展各項電子交易所須之電子認證服務及相關標準.

我國政府公開金鑰基礎建設 如下圖 政府憑證 總管理中心 財團 社團法人 內政部 憑證管理中心 憑證管理中心 政府測試 工商 憑證管理中心

內政部憑證管理中心核發之憑證為自然人憑證;亦可稱為 “電子身分證”, 它透過IC卡儲存個人相關資訊; 包括 個人憑證及私密金鑰,後者無法從卡片讀出(僅能直接在卡上參與計算),而保證其安全性. 一般磁卡約可存120 bytes之資料,但是 IC卡則可存 1K, 2K, 4K, 8K, 16K, 32K等資料. IC卡之使用者之身分辨識是以個人密碼(PIN)之核驗方式行之;因此不怕遺失. 智慧卡晶片內的重要模組包括: CPU 、RAM 、FLASH 、RSA 、DES與AES加解密輔助運算器(Cryptographic Coprocessor) 、以及針對晶片內部保護的類比電路等,組成一個系統整合型的單晶片系統電路(SOC; System-On-Chip). 此系統晶片,提供了智慧卡作業系統(COS; Card Operating System) 發展的硬體平台.

與PC上之作業系統不同的是IC卡上的COS是“燒”(Mask) 在IC卡的ROM或FLASH中. 目前國內廠商所研發的智慧卡晶片,除具備有對稱式密碼演算法DES 、Triple DES及AES演算能力外,也具備了非對稱式密碼演算法RSA的電子簽章功能.此外,也內建亂數產生器於此晶片中,提供與讀卡機或遠端主機作挑戰與回應協定( Challenge and Response Protocol) 所需之亂數來源.

Schnorr's DS 系統已知 簽署作業 驗證 {CRYPTO’89} r = gk = gs + xe = gs gxe = gsye 1. 大質數 P 及 q 滿足 q|P-1, q 2160 及 P  2512 2. g  Zp 且滿足 gq = 1 mod P, g  1 3. h 為 one-way hash fun. 4. Signer Bob 之私鑰 x , 1 < x < q 5. Bob 之公鑰 y = gx mod P. 1. Bob 任選一整數 k , 1 < k < q, 並求出 r = g k mod P 2. 求出 e = h(r, M) 3. 求出 s = k - x e mod q, (e, s) 即 Bob 對 M 之簽署文. 簽署作業 r = gk = gs + xe = gs gxe = gsye Meanwhile since q|P-1, the exponential part should be computed with mod q for the size of computations. 驗證者(Verifier) Alice 求出: 1. Let r’ = gs ye mod P 2. 檢查 h(r’ , M) = e 驗證 ?  r’ = gsye = gk-xegxe = gk = r (mod P) h(r’ , M) = h(r , M) = e

ElGamal-type Signatures Observations 1. 此法之簽署文較ElGamal 為短, 因為 e 的長度由 h函數決定, s 的長度小於 |q |. 2. Schnorr’s DS 中之g ( > 2160) 非 ZP 中之原根(其序為 P-1), 故安全不若 ElGamal’s DS(然而其計算較小而省). ElGamal-type Signatures ElGamal簽章法乃以DLP為基,其systematic design 詳情可見 於“第八屆全國資訊安全會議論文集”之韓亮教授大作 pp. 1-16. 一般而言, 除了{ r, s, M, k, x } 五參數外,尚有one-way hash fun h 亦存在於簽章環境中,而簽署之對象是 h(M), 只是論文中已簡化成 M矣. 利用此五參數之排列組合,即可最少組合至 18 種簽章之多,當然此中有優劣之別. 另, since DSA is a special form of the original ElGamal scheme, which utilizes another parameter q, where q is a prime factor of P-1, all 18 ElGamal-type variants can be easily converted into DSA-type variants. 次頁簡介六種 DSA-type variants, 而其后再介紹 18種 ElGamal-type variants.

DSA-type Variants

右 = gs ym = gs (gx)m = gs+xm = g k r’ = 左 (一) rr’ = gs ym ? (mod p) 左 = ( g k)r’ = g k r’ 右 = gs ym = gs (gx)m = gs+xm = g k r’ = 左

ElGamal-type variants 前提如 DSA-type form, 然而 此處   g , {r, s} is the digital signature of message m, k and x are secrets of the signer. In ElGamal original scheme, there are five parameters {r, s, m, k, x} in the signature signing equation. Although additional generalization and variants can generate more than 13,000 variants, but these 18 variants are the most efficient variants since each of them permutes these five parameters directly. 1. mx = rk + s mod p-1 ym = r r s mod p 2. mx = sk + r mod p-1 ym = r s r mod p 3. rx = mk + s mod p-1 yr = r m s mod p 驗證第一種: mx = rk + s mod p-1 ym = r r s mod p 左 = ym = (gx)m = gxm 右 = r r s = (gk)r gs = gkr+s = gxm = 左

prefer 4. rx = sk + m mod p-1 yr = r m s mod p 5. sx = rk + m mod p-1 ys = r r m mod p 6. sx = mk + r mod p-1 ys = r m r mod p 7. rmx = k + s mod p-1 yr m = r s mod p 8. x = mrk + s mod p-1 y = r mr s mod p 9. sx = k + mr mod p-1 ys = r mr mod p 10. x = sk + rm mod p-1 y = r s r m mod p 11. rmx = sk + 1 mod p-1 yr m = r s  mod p 12. sx = rmk + 1 mod p-1 ys = r mr  mod p 13. (r+m)x = k + s mod p-1 yr+m = r s mod p 14. x = (m+r)k + s mod p-1 y = r m+r s mod p 15. sx = k + (m+r) mod p-1 ys = r m+r mod p 16. x = sk + (r+m) mod p-1 y = r s m+r mod p 17. (r+m)x = sk + 1 mod p-1 yr+m = r s  mod p 18. sx = (r+m)k + 1 mod p-1 ys = r m+r  mod p prefer

undeniable signature interactively 1. 此簽章法無法將明文M還原. ( D. Chaum & H. van Antwerpen at CRYPTO’89) undeniable signature Known facts: a large prime P, and a primitive element g, are made public, and used by a group of signers. Alice has a private key, x, and a public key , gx. To sign a message, Alice computes z = Mx. That’s all she needs to do. Verification is a little more complicated: (B 要 A 印證 z 是她簽署的) (1) Bob chooses two random numbers, a and b, both less then P, and sends Alice: c = z a(gx)b (mod P) (2) Alice computes x -1 (mod P-1), and sends Bob: d = cx -1 (mod P) (3) Bob confirms that d  Magb (mod P) (此式子可馬上導證;讀者自己試試看) If it is, he accepts the signature as genuine. interactively 1. 此簽章法無法將明文M還原. 2. 除了signer Alice 外,無人知道其私鑰 x , 故不能否認簽署之事實. 3. 下一方法是D.Chaum 在EUROCRYP90所提之zero-knowledge undeniable signature .

ZKUS ( D. Chaum at EUROCRYPTO’90) Known facts: a large prime P, and a primitive element g, are made public, and used by a group of signers. Alice has a private key, x, and a public key , gx. To sign a message, Alice computes z = Mx. ① To verify a signature: (B 要 A 印證 [with Zero-Knowledge] z 是她簽署的) (1) Bob chooses two random numbers, a and b, both less then P, and sends Alice: c = Magb (mod P) ② (2) Alice chooses a random number, q, less than P, and computes and sends to Bob: s 1 = cg q s 2 = (cg q )x (mod P)③ (3) Bob sends Alice a and b, so that Alice can confirm that Bob did not cheat in step (1). (4) Alice sends Bob q, so that Bob can use Mx and reconstructs s 1 and s 2. If s 2 = (gx)b+q za (此式子可馬上導證;讀者自己試試看) If they are, he accepts the signature as genuine. ① ② ③

數學式推導 d  Magb (mod P) ? (此式子[指page 21 之方法]可馬上導證): d = cx -1 = (za (gx)b) x -1 = za/x (g1)b = Mx(a/x) gb = Magb (mod P) s 2 = (cg q )x = c x g xq = (Magb )x g xq = Maxgbx g xq = g xq+xbMax = (gx)b+q za s 2 = (gx)b+q za ? (此式子[指page 22 之方法]可馬上導證)

It is weird . . .

Nyberg-Rueppel Signature 系統已知 Let P be a large prime number, Q be a prime factor of P-1, and G be a primitive element to mod P.{ all these three are known to public}, Now, the signer holds SK[1, Q-1] as secret key and PK=GSK mod P as public key , plaintext M [1, P-1] and a random number r [1, Q-1] . 簽署作業 SG1 = M * G r mod P SG2 = SK * SG1 + r mod Q 任何人可用下列方式驗證送方身份並且可 recover message M : M  G -SG2 * PK SG1 * SG1 mod P  G -SK*SG1 -r * G SK * SG1 * M * G r mod P  M * G -SK*SG1 -r + SK * SG1 +r mod P 驗證 ? 1994年 Carmenisch, Piveteau & Stadler(CPS) 利用上述精神提出一盲簽章法

利用Euclid's algorithm.(所謂法二) D. Chaum (1982) Blind Signature 系統參數: signer 之 public key (e, n), private key d, p, q (n=p*q). 簽署程序: A 請 B 簽署一份信息M,然 B 不被告知 M 之內容 (1) A 任選一亂數 r(即 blinding factor), 1< r < n, 且計算 t = M * r e mod n , 給B. (2) B 簽署 t, 即  = td = (M* r e) d mod n, 給A. (3) A 計算(unblind)出 M 之簽章為: s =  * r -1 = td * r -1 = M d (mod n). 1. r -1 如何求出 ? [根據下述探討知 必另有求反元素之方法] If gcd(a,n)=1, then how to compute x s.t. a*x mod n = 1? @ 只需將 x 設為 x = a(n)-1 mod n 即可! { 不必求 (n) ? } 2.盲簽章應用於 digital money, electronic voting. 3.即使 A 公佈了 M 與 s , B 也無法找出 (M, s) 與 (t,  )之對應關係; 即 signer 無從追蹤明文 與當時盲簽章之相互關係. Think 利用Euclid's algorithm.(所謂法二)

CPS blind-signature 任何人可以下述驗證 系統參數: signer holds SK[1, Q-1] as secret key and PK=GSK mod P as public key , and a random number r [1, Q-1] . signer requester 1 K = G r mod P, r[1, Q-1] 任選兩亂數(盲因子) ,  [1, Q-1] 算 SG1 = M * G * K mod P C = SG1 *  -1 mod Q 2 SGC = C * SK + r mod Q 3 算 SG2 = SGC *  +  mod Q (4) 任何人可以下述驗證 (5) ? M  G -SG2 * PK SG1 * SG1 mod P = (G -SGC *  - ) * (GSK * SG1) * (M * G * K ) mod P = (G -(C *SK + r)*  - ) * (GSK * SG1) * (M * G * G r *  ) mod P = (G -SG1*SK -r *  - ) * (GSK * SG1) * (M * G * G r *  ) mod P = M * G -SG1*SK -r *  -  +SG1*SK +r *  +  mod P.