【文章內(nèi)容簡(jiǎn)介】 nce amp。 Technology, Peking University 40 Certificate subject amp。 issuer attributes ?這類(lèi)擴(kuò)展提供關(guān)于證書(shū)發(fā)行者和持有者的別名或其他信息 (公司的郵政地址 ,圖片等 ) ?Subject alternative name: 證書(shū)持有者的別名信息 ,如在 ,EDI等中的別名 . ?Issuer alternative name: 證書(shū)發(fā)行者的別名 ?Subject directory attributes: 證書(shū)持有者的目錄服務(wù)屬性 Institute of Computer Science amp。 Technology, Peking University 41 Certification path constrains ?這類(lèi)擴(kuò)展僅用于 CA之間的簽署證書(shū) ,限制被簽署 CA可以簽發(fā)的證書(shū)類(lèi)型 ,或者允許其出現(xiàn)在后續(xù)的證書(shū)鏈中 ?Basic constraint: 標(biāo)識(shí)證書(shū)持有者是否可以作為CA,如果是 ,一個(gè)證書(shū)鏈長(zhǎng)度可以給出 . ?Name constrains: 指示一個(gè)后續(xù)的證書(shū)持有者的名字必須出現(xiàn)的名字空間 ?Policy constrains: 關(guān)于證書(shū)鏈的后續(xù)節(jié)點(diǎn)的策略指示 ? Institute of Computer Science amp。 Technology, Peking University 42 識(shí)別協(xié)議引言 (1) ?用戶登錄的實(shí)現(xiàn) : ?初始化 : 用戶設(shè)置密碼 , 計(jì)算機(jī)記到磁盤(pán)上 ?登錄 : 用戶輸入密碼 ,計(jì)算機(jī)跟記住的密碼比較 ?問(wèn)題 : 訪問(wèn)磁盤(pán)就可能獲得用戶的密碼 ?用戶登錄實(shí)現(xiàn)的改進(jìn) ?初始化 : 用戶設(shè)置密碼 , 計(jì)算機(jī)進(jìn)行 hash,把 hash值記到磁盤(pán)上 ,立即銷(xiāo)毀用戶密碼 ?登錄 : 用戶輸入密碼 ,計(jì)算機(jī)執(zhí)行 hash,再跟記住的 hash值比較 ?問(wèn)題 : 攻擊者輸入一個(gè)串 ,產(chǎn)生 hash,訪問(wèn)磁盤(pán)并用該 hash替換用戶密碼的 hash,可假冒用戶登錄 ? Institute of Computer Science amp。 Technology, Peking University 43 識(shí)別協(xié)議引言 (2) ?用戶登錄實(shí)現(xiàn)的再改進(jìn) : ?初始化 : 用戶設(shè)置密碼 , 計(jì)算機(jī)進(jìn)行 hash,用 hash值對(duì)一段已知明文以及用戶的賬號(hào)等關(guān)鍵數(shù)據(jù)進(jìn)行加密并保存 ,立即銷(xiāo)毀用戶的密碼以及其 hash值 ?登錄 : 用戶輸入密碼 ,計(jì)算機(jī)執(zhí)行 hash,再對(duì)同樣已知明文加密 ,與保存的加密結(jié)果比較 ,若相同 , 則試圖解密用戶賬號(hào)等關(guān)鍵數(shù)據(jù) ?攻擊 : 攻擊者輸入串 ,產(chǎn)生假冒 hash并用其加密已知明文 ,訪問(wèn)磁盤(pán)并用該加密結(jié)果替換原來(lái)的已知明文的加密結(jié)果 ,則計(jì)算機(jī)執(zhí)行第一步會(huì)通過(guò) ,但 假冒的 hash不能解密用戶的賬號(hào)等關(guān)鍵數(shù)據(jù) Institute of Computer Science amp。 Technology, Peking University 44 識(shí)別協(xié)議引言 (3) ?安全的識(shí)別協(xié)議應(yīng)該滿足 : ?證明者 A能向驗(yàn)證者 B證明他的確是 A ?在證明者 A向驗(yàn)證者 B證明其身份后 ,驗(yàn)證者 B不能假冒 A(向第三方證明他是 A) ?證明者 A在證明中泄漏的信息越少越好 ,驗(yàn)證者B從驗(yàn)證中獲得的關(guān)于 A的信息越少越好 ?如果證明者 A除了向 B證明自己是 A外沒(méi)有泄漏任何其他信息 ,則屬于“身份的零知識(shí)證明” ? Institute of Computer Science amp。 Technology, Peking University 45 剩余類(lèi) ?我們?cè)眠^(guò)模 n的剩余類(lèi)一些結(jié)論 ,現(xiàn)在給出正式的定義 . ?對(duì)任何非 0整數(shù) n?Z(全體整數(shù)集合 ),集合Zn={0,1,2,…,n 1}稱(chēng)為模 n的最小剩余集 ?Zn中可“自然”地定義加法和乘法運(yùn)算 (模 n運(yùn)算 ): (a+b)|Zn := ((a+b)|Z mod n) (a?b)|Zn := ((a?b)|Z mod n) ?容易知道上述運(yùn)算滿足交換率 ,結(jié)合率和分配率 ?加法的負(fù)元素 : (a)|Zn := (na)|Z,并定義減法為 : (ab)|Zn := (a+(b))|Zn := ((ab)|Z mod n) ?乘法的逆元素 : 若 a?Zn且 ?x使得 (a?x)|Zn=1,則稱(chēng)說(shuō) a是可逆的且稱(chēng) x是 a的逆 ,記作 a1 ? Institute of Computer Science amp。 Technology, Peking University 46 逆的唯一性 ?結(jié)論 : Zn中一個(gè)元素的逆若存在 ,則必是唯一的 ?證明 : 假設(shè) a,x,y?Zn, a?x = 1且 a?y = 1 則 x = x?1 = x?(a?y) = (x?a)?y (結(jié)合律 ) = (a?x)?y (交換律 ) = 1?y = y ? x = y ?Zn中除法運(yùn)算 : 若 a?Zn中且 a可逆 ,則 (b/a)|Zn := (b?(a1))|Zn ?Zn中 的加 ,減 ,乘 ,除運(yùn)算跟 Z中加 ,減 ,乘 ,除運(yùn)算有非常相似的性質(zhì) Institute of Computer Science amp。 Technology, Peking University 47 逆存在的充分必要條件 (1) ?結(jié)論 : Zn中元素 a的逆存在 ? gcd(a,n)=1 ?證明 : 假定 Zn中元素 a的逆存在 那么 ?b?Zn使得 (a?b)|Zn = 1 ?(a?b)|Z ? 1 mod n ? ?整數(shù) k,使得 (a?b)|Z = (k?n+1)|Z ?(a?bk?n)|Z = 1 若 a,n有大于 1的共因子 d,則左式能被 d整除 ,而右式等于 1(不能被 d整除 !),矛盾 .? gcd(a,n) = 1。 反過(guò)來(lái) ,假定若 gcd(a,n) = 1 擴(kuò)展的 Euclidean算法可算出 a的逆 (從而證明了逆的存在性 ),下面的方法也能證明逆的存在 . Institute of Computer Science amp。 Technology, Peking University 48 逆存在的充分必要條件 (2) 令集合 S={(a?x)|Zn:對(duì)所有 x屬于 Zn},顯然 S?們要證明 S=Zn,這只要證明 S和 Zn的元素個(gè)數(shù)一樣多 ,為此只要證明任意兩個(gè) (a?x)|Zn不等 ,即 : ?x ? y?Zn, 必有 (a?x)|Zn ? (a?y)|Zn 否則 , (a?(xy))|Zn = (a?x)|Zn (a?y)|Zn = 0 ? n|(a?(xy)),由于 gcd(a,n)=1,因此 n|(xy), 但是 , 0 ? x ? y n, n|(xy)不可能成立 . 由此可知 S=Zn ?S包含元素 1 ? ?b?Zn使得 (a?b)|Zn=1 ? a的逆存在 Institute of Computer Science amp。 Technology, Peking University 49 逆的計(jì)算 ?定義 : Zn*={a?Zn且 a可逆 }={a?Zn且 gcd(a,n)=1} ?結(jié)論 : |Zn*| = ?(n), ?(n)是 Euler函數(shù) . ?若 p是素?cái)?shù) ,則 Zp*={1,2,…,p 1}=Zp\{0} ?由 Euler定理 可知 , ?a?Zn*,則 a?(n) ? 1 mod n,從而有 : a1=a?(n)1 mod n ?盡管 Euler定理給出了的 a1計(jì)算公式 ,但這個(gè)公式的計(jì)算效率是很低的 ,擴(kuò)展的 Euclidean算法更有效 . Institute of Computer Science amp。 Technology, Peking University 50 二次剩余 ?二次剩余 : 設(shè) a?Zn*,若 ?x使得 x2 ? a mod n,則稱(chēng)a是 n的一個(gè)二次剩余 ,x稱(chēng)為 a的一個(gè)平方根 ,n的二次剩余集合記為 Qn, n的二次非剩余集合記為 NQn,則 NQn= Zn*\Qn. ?a?Zn* ? gcd(a,n)=1, 若 x2 ? a mod n,那么顯然gcd(x,n)=1 ? x?Zn* ,即二次剩余的平方根還是可逆元素 . ?許多因子分解算法利用二次剩余進(jìn)行 ?結(jié)論 :若 x是 a的平方根 ,則 nx是也是一個(gè)平方根 ?問(wèn)題 : 二次剩余的平方根就是兩個(gè)嗎 ? ?若 n是奇素?cái)?shù) ,則結(jié)論成立 。若 n是一個(gè) RSA模 (即n=p?q, p?q奇素?cái)?shù) ),則二次剩余的平方根為四個(gè) . Institute of Computer Science amp。 Technology, Peking University 51 素?cái)?shù)模的平方根的個(gè)數(shù) ?結(jié)論 :若 p奇素?cái)?shù) ,則 p的每個(gè)二次剩余恰有兩個(gè)平方根 ?證明 : 先證明單位元 1恰有兩個(gè)平方根 :1和 p1. 若 u(0up)是 1的平方根 ,那么 u2 ? 1 mod p ? p|(u21) ? p|(u+1) 或者 p|(u1) 0up?0u+1?p,故 p|(u+1) ? p=(u+1) ? u = p1 0up?0?u1p,故 p|(u1) ? u1=0 ? u = 1. ?a是 p的二次剩余 ,x是 a的一個(gè)平方根 ,若 y也是 a的平方根 ,則 x2 ? a ? y2 mod p ?(x1y)2 ? 1 mod p ?x1y = 1或者 p1 ?y=x或者 y=(p1)x mod p = px Institute of Computer Science amp。 Technology, Peking University 52 RSA模的平方根的個(gè)數(shù) (1) ?結(jié)論 :若 n是 RSA模 (即 n=p?q, p?q奇素?cái)?shù) ),則 n的每個(gè)二次剩余恰有四個(gè)平方根 ?證明 : 先證明單位元 1恰有四個(gè)平方根 :即除了 1和 pq1外還有兩個(gè) . 若 u(0un)是 1的平方根 ,那么 u2 ? 1 mod n ? n|(u21) ? n|(u+1)(u1), 注意 n=pq,只有四種可能 : 情形 ?: n|(u+1) ? n=u+1 ? u=n1=pq1 情形 ?: n|(u1) ? u1=0 ? u = 1 情形 ?: p|(u+1),q|(u1) 情形 ?: p|(u1),q|(u+1) 先證明 ? Institute of Computer Science amp。 Technology, Peking University 53 RSA模的平方根的個(gè)數(shù) (2) ?情形 ?: p|(u+1),q|(u1) 首先 ,這樣的 u唯一 : 若 v也滿足上述條件 ,則 p|(u+1),p|(v+1)?p|(uv)。 q|(u1),q|(v1)?q|(uv) ? pq|(uv) ? u ? v mod n 其次 ,這樣的 u存在 : gcd(p,q)=1 ? ?整數(shù) s,t,使得 sp+tq = 1,令 u = (sptq mod n),注意 n=p?q,則 u+1 ? sptq+1 mod n ? sptq+(sp+tq) mod n ? 2sp mod n ? p|(u+1) u1 ? sptq1 mod n ? sptq(sp+tq) mod n ? 2tq mod n ? q|(u1) 類(lèi)似可證明 ?且 u = (sp+tq) mod n 從而單位元恰有四個(gè)平方根 . Institute of Computer Science amp。 Technology, Peking University 54 RSA模的平方根的個(gè)數(shù) (3) ?a是 n的二次剩余 ,x是 a的一個(gè)平方根 ,若 y也是 a的平方根 ,則 x2 ? a ? y2 mod n ?(x1y)2 ? 1 mod n 這說(shuō)明 x1y是單位元的平方根 ,由上面的證明 ,單位元恰有四個(gè)平方根 ,所以 y恰有四個(gè)不同的值 ,注意到單位元的平方根中有一個(gè)就是單位元自己 ,所以四個(gè) y值中恰有一個(gè)與 x相同 . 從而結(jié)論成立 . Institute of Computer Science amp。 Technology, Peking University 55 素?cái)?shù)模的二次剩余的個(gè)數(shù) ?結(jié)論 :若 p奇素?cái)?shù) ,則 p的二次剩余恰有 (p1)/2個(gè) . ?證明 : 先證明 |Qp| ? |Zp*|/2 由于 p的每個(gè)二次剩余恰有兩個(gè)平方根 ,假如|Qp||Zp*|/2, 則 Qp中元素的平方根的總個(gè)數(shù)大于|Zp*|,而這些平方根都屬于 Zp*且兩兩不相同 ,這是不可能的 ,故 |Qp|?|Zp*|/2。 再證明 |Qp| ? |Zp*|/2. 把 Zp*的每個(gè)元素自乘 (平方 ),結(jié)果當(dāng)然都是二次剩余 ,注意到不可能有兩個(gè)以上元素的自乘是相同的 (因?yàn)槊總€(gè)二次剩余只有兩個(gè)平方跟 ),所以 |Qp| ? |Zp*|/2。 故 |Qp| = |Zp*|/2 = (p1)/2 ?推論 :若 p奇素?cái)?shù) ,則 p的二次非