1/3 考試說明

• 選擇題断傲，10道脱吱，共10分
• 填空題，10道认罩，共20分
• 簡答題箱蝠，5道，共30分
• 計算題垦垂，3道闺金，共30分
• 論述題攻谁，1道笤喳，共10分

2/3 考前復習

（有些計算錯誤懶得改了勺疼，方法都是對的）

黑板上的題

復習資料

3/3 學習筆記

一、密碼學概論

• 信息安全和密碼學

1）秘密通信的手段
① 信道保護：如信使傳遞页慷、密寫憔足、縮微攝影、專線電話
② 密碼保護：如電報加密酒繁、傳真加密滓彰、語音加密、圖象加密
2）信息安全的目標
機密性州袒、認證性找蜜、數(shù)據(jù)完整性、不可否認性稳析、可用性
3）密碼學的重要性
密碼技術是一門古老的技術，信息安全目標要依賴各種安全機制來實現(xiàn)弓叛，而許多安全機制則需要依賴于密碼技術
4）加密系統(tǒng)模型

明文：發(fā)送方將要發(fā)送的消息
密文：明文被變換成看似無意義的隨機消息
加密：明文變換成密文的過程稱為加密
解密：密文恢復出原明文的過程稱為解密
加密算法：對明文進行加密時所采用的一組規(guī)則
解密算法：對密文進行解密時所采用的一組規(guī)則
加密和解密的操作通常都是在一組密鑰控制下進行的彰居，分別稱為加密密鑰和解密密鑰
密碼系統(tǒng)是一個五元組（P，C撰筷，K陈惰，E，D）毕籽，滿足條件：
① P是可能明文的有限集;（明文空間）
② C是可能密文的有限集;（密文空間）
③ K是可能密鑰的有限集;（密鑰空間）
④ 對于 k∈K抬闯，有加密算法 ek∈E 和解密算法 dk∈D，使得 ek：P→C 和 dk：C→P
分別為加密关筒、解密函數(shù)溶握。滿足 dk（ek（x））=x，這里 x∈P
5）密碼體制的原則和分類
柯克霍夫原則
單鑰體制（One key system）：加密密鑰和解密密鑰相同蒸播。
雙鑰體制（Two key system）：加密密鑰和解密密鑰不同睡榆。
密碼分析包含：基于算法性質的分析萍肆、窮舉密鑰分析
6）密碼體制的攻擊

二、數(shù)學基礎

• 因數(shù)和倍數(shù)

12的因子：1胀屿，2塘揣，3，4宿崭，6亲铡，12
12的真因子：2，3葡兑，4奖蔓，6
① 對所有a，1 | a铁孵，a | 0锭硼，a | a
② 若a | b且b | c，則a | c
③ 若a | b蜕劝，則對任意的c檀头，有ac | bc
④ 若ac | bc且c≠0，則a | b
⑤ 若a | b且a | c則對任意的m岖沛，n有al(bm +cn).

• 素數(shù)和合數(shù)

一個大于1且只能被1和它本身整除的整數(shù)暑始，稱為素數(shù);否則稱為合數(shù)
12=3×4，其中3是12的素因數(shù)婴削，而4是12的合因數(shù)

• 最大公因數(shù)

若gcd(m廊镜，n)=1，稱m唉俗，n是互素的
若a=bq+r嗤朴，0<r<b，則(a虫溜，b)=(b雹姊，r)
若(a，b)=d衡楞，則(ald吱雏，b | d)=1
歐幾里得算法：若a=bq+r，0<r<b瘾境，則 gcd(a歧杏，b)=gcd(b，r)=gcd(b迷守，a mod b)
例：gcd(372犬绒，164)=gcd(164，372mod164)
=gcd(164兑凿，44)=gcd(44懂更，164mod44)
=gcd(44眨业，32)=gcd(32，44mod32)
=gcd(32沮协，12)=gcd(12龄捡，32mod12)
=gcd (12，8)gcd(8慷暂，12mod8)
=gcd (8聘殖，4)=gcd(4，8mod4)=gcd(4行瑞，0)=4

• 模運算

117=31·3+24奸腺，117mod31=24

• 乘法逆元

若 xy mod m = 1，則稱y是x模m的乘法逆元
通常記為：y = x^-1 mod m

• 一次同余式

定義： ax ≡ b(mod m)
若x0滿足上式血久，則x ≡ x0(mod m)稱為同余方程組的解
若(a突照，m)=1，則恰有一解 x ≡ ba^-1(mod m)

三氧吐、古典密碼學

• 古典密碼技術

1）古典密碼的分類：代換密碼讹蘑，置換密碼
① 代換密碼：將明文元素映射成密文的元素
代換密碼分為單字母代換、多字母代換
單字母代換分為單表代換筑舅、多表代換座慰、多名代換
② 置換密碼：將明文元素的位置進行的置換
置換密碼通過改變明文消息各元素的相對位置，但明文消息元素本身的取值或內(nèi)容形式不變

2）Caesar 密碼：26個英文字母與整數(shù)0~25對應翠拣，Caesar 密碼密鑰數(shù)量過少版仔。
將Caesar 密碼一般化，取任意的整數(shù)k作為密鑰：
加密變換：c = E(k误墓，p) = (p+k)(mod26)
解密變換：p = D(k蛮粮，c) = (c-k)(mod26)
一般單表替代密碼算法特點：
① 密鑰空間K很大，|K| = 26!
② 移位密碼是替換密碼的一個特例谜慌，它僅含26個置換做為密鑰空間然想。
③ 密鑰n不便記憶，通常會采用密鑰短語密碼：選用英文短語或單詞串作為密鑰畦娄，去掉其中重復的字母，其它字母依次寫于此字母串后弊仪，就可構造出一個字母替代表熙卡。
3）仿射密碼：一種線性變換。仿射密碼的明文空間和密文空間與移位密碼相同励饵，但密鑰空間為 K = {(k1驳癌，k2)|k1，k2∈Z??役听，gcd(k1颓鲜，26) = 1};
對任意 m∈M表窘，c∈C，k = (k1甜滨，k2)∈K乐严，定義加密變換和解密變換為：
c = ek(m) = k1m+k2 (mod26)
m = dk(c) = k1^-1(c-k2) (mod26)

四泡嘴、分組密碼

• 分組密碼概述

1）分組密碼具有速度快甫恩、易于標準化、便于軟硬件實現(xiàn)等待點酌予。它是信息安全中實現(xiàn)數(shù)據(jù)加密和認證的核心體制磺箕。
2）分組密碼的思想：將明文消息編碼后的序列分成長為n的組，各組分別在密鑰k控制下變換成等長的輸出序列
3）在相同密鑰下霎终，各組的變換是等同的滞磺，所以只需研究任一組的變換規(guī)則。這種密碼實質上是字長為n的數(shù)字序列的代換密碼莱褒。
針對安全性的一般設計原則：
① 明文分組長度和密鑰長度望盡可能大击困。
② 混淆原則：是指密鑰、明文广凸、密文之間的依賴關系盡可能的復雜阅茶。
③ 擴散原則：密鑰或明文的每一位影響密文的許多位以便隱蔽明文的統(tǒng)計特性。如古典密碼中的 hill 密碼
迭代密碼：Feistel 結構（S盒代換谅海，P盒置換）脸哀、SPN結構（S變換混淆，P變換擴散）

• DES 與 AES

1）DES 歷史
1971年扭吁，IBM 由 Horst Feistel 領導的項目組研究出 LUCIFER 算法撞蜂。并應用于商業(yè)領域。
1973年侥袜，美國標準局征求標準蝌诡，IBM提交結果。
1977年枫吧，被選為數(shù)據(jù)加密標準浦旱。
1994年，美國決定98年12月以后不再使用DES算法
2）DES 概述
DES是一種明文分組為64比特九杂，有效密鑰56比特颁湖，輸出密文64比特的宣蠕，具有16輪迭代的分組對稱密碼算法。DES由初始置換甥捺、16輪迭代抢蚀、初始逆置換組成。DES的加解密算法相同涎永，只是加解密子密鑰的使用順序相反思币。

2）多重加密算法
三重DES的多重加密算法是DES的一個重要的改進算法。

3）AES
AES算法具有128比特的分組長度,并支持128羡微、192谷饿、256比特的密鑰長度。字節(jié)的運算：

AES 的評估標準
① 安全性：算法抗密碼分析的強度,穩(wěn)定的數(shù)學基礎,算法輸出的隨機性,與其他候選算法比較的相對安全性妈倔。
② 代價：許可要求,在各種平臺上的計算效率和內(nèi)存空間的需求博投。
③ 算法和實現(xiàn)特性：靈活性、硬軟件適應性盯蝴、算法的簡單性等毅哗。

• 分組密碼的工作模式

美國在 FIPS 中定義了五種工作模式：電碼本模式(ECB)、密碼分組鏈接模式(CBC)捧挺、輸出反饋模式(OFB)虑绵、密碼反饋模式(CFB)、計數(shù)器模式(CTR)

五闽烙、序列密碼

• 5-1 密碼學中的隨機數(shù)

1翅睛、隨機數(shù)的使用
通常的序列密碼中，密鑰序列是偽隨機序列黑竞，它的產(chǎn)生容易且有較成熟的理論工具捕发，是當前通用的密碼系統(tǒng)。
序列密碼的保密性取決于密鑰的隨機性很魂。如果密鑰是真正的隨機數(shù)扎酷，則在理論上就是不可破譯的。
目前一般采用偽隨機序列來代替隨機序列作為密鑰序列遏匆，也就是序列存在著一定的循環(huán)周期法挨。
2、偽隨機數(shù)產(chǎn)生器
由任何偽隨機數(shù)生成器返回的數(shù)目會受到0~N之間整數(shù)數(shù)目的限制幅聘》材桑可以得出的數(shù)字總是處于0和1之間。
3喊暖、基于密碼算法的隨機數(shù)產(chǎn)生器
① 軟件方法：線形擬合生成器：X(n+1)=(aXn+b)mod c
② 硬件方法：ComScire QNG：使用并行端口連接到PC的外部設備惫企，每秒鐘生成20000位撕瞧。
4陵叽、偽隨機數(shù)的評價標準
① 測試套件：George Marsaglia的DIEHARD軟件包 ② 無法預測狞尔。③ 不能可靠地重復產(chǎn)生。

• 5-2 流密碼的分類

1巩掺、自同步序列密碼：該算法的密碼復雜性在于輸出函數(shù)偏序，它收到內(nèi)部狀態(tài)后生成密鑰序列位。
2胖替、同步序列密碼：具有自同步能力研儒，強化了其抗統(tǒng)計分析的能力。
缺點：有n位長的差錯傳播独令，它們會使系統(tǒng)失去同步而立即被發(fā)現(xiàn)端朵。

• 5-3 常用的序列密碼算法

① A5序列密碼算法
由三個LFSR組成，集控制與停走于一體的鐘控模型燃箭。但是A5算法沒有完全公開冲呢，各種資料的描述也不盡相同，重要是第二招狸、三個LFSR的聯(lián)接多項式以及鐘控的位置敬拓。
② SEAL序列密碼算法
需要8個32位的寄存器和約8M的內(nèi)存，它不基于LFSR裙戏，而是一個偽隨機函數(shù)簇（PRF）乘凸，將明文的位置變成一個隨機串。
③ RC4序列密碼體制
RC4為RSA設計累榜，是一個可變密鑰長度营勤、面向字節(jié)操作的序列密碼。
基本思想：對于n位長的字信柿，它總共2^n個可能的內(nèi)部置換狀態(tài)矢量S冀偶，這些狀態(tài)是保密的，密鑰流K由S中N個元素按照一定方式選出一個元素而生成渔嚷。每生成一個K值进鸠，S就被重新置換一次。

• 5-4 密鑰流的局部隨機性檢驗

1形病、真隨機序列的特性
統(tǒng)計的隨機性客年、不可預測性、不可再生性漠吻。
真隨機序列特性雖好量瓜，但難以在實際密碼系統(tǒng)中應用，實際密碼系統(tǒng)中使用的密鑰流都是偽隨機序列途乃。
2绍傲、偽隨機序列的統(tǒng)計特性
平衡特性、游程特性、自相關特性
3烫饼、密鑰流的局部隨機性檢驗
頻數(shù)檢驗猎塞、序列檢驗、撲克檢驗杠纵、游程檢驗荠耽、自相關檢驗
4、序列密碼的設計原則
最基本的設計原則是“密鑰流生成器的不可預測性”比藻，它可分解為下述基本原則：
長周期铝量、高線性復雜度、統(tǒng)計性能良好银亲、足夠的“混亂”慢叨、足夠的“擴散”、抵抗不同形式的攻擊务蝠。

六插爹、Hash函數(shù)和消息認證

• 6-1 Hash函數(shù)

一、Hash函數(shù)的概念
1请梢、Hash函數(shù)（雜湊函數(shù)）是密碼學的一個基本工具赠尾，在數(shù)字簽名、身份認證毅弧、消息的完整性檢測等方面有著重要的應用气嫁。
2、它是一種公開函數(shù)够坐，用于將任意長的消息M映射為較短的寸宵、固定長度的一個值H（M）作為認證符。H（M）稱為雜湊碼元咙。
3梯影、雜湊碼是消息中所有比特的函數(shù)，因此提供了一種錯誤檢測能力庶香，即任何一個比特改變都會使雜湊碼發(fā)生改變甲棍。
特點：H打上了輸入數(shù)字串的烙印，為數(shù)字指紋（Digital Finger Print）
4赶掖、散列函數(shù)的性質
① 一般雜湊函數(shù)H（m）算法公開感猛，不需要密鑰。
② 具有數(shù)據(jù)壓縮功能奢赂，可將任意長度的輸入數(shù)據(jù)轉換成固定長度的輸出陪白。
③ 對任何給定的m，h（m）易于計算膳灶。
二咱士、Hash函數(shù)結構
算法中重復使用某個函數(shù) f。函數(shù) f 的輸入有兩項，一項是上一輪的輸出CVi-1序厉，稱為鏈接變量拆吆。另一項是算法在本輪b位的輸入分組mi。

三脂矫、Hash函數(shù)應用
在密碼學和數(shù)據(jù)安全技術中，它是實現(xiàn)有效霉晕、安全可靠數(shù)字簽字和認證的重要工具庭再，是安全認證協(xié)議中的重要模塊。

• 6-2 Hash算法

MD5牺堰、SHA-1是當前國際通行的兩大密碼標準拄轻。MD5由圖靈獎獲得者兼 RSA的創(chuàng)始人Rivest設計；SHA-1由美國制定密碼算法的標準機構 NIST與 NSA設計伟葫。
一恨搓、MD5算法
輸入：任意長度的消息
輸出：128位消息摘要
處理：以512位輸入數(shù)據(jù)塊為單位

二、SHA算法
SHA-1筏养，SHA-256 的分組大小是512 bit
SHA-384斧抱，SHA-512 的分組大小是1024 bit
SHA-1 輸出摘要是160 bit
SHA-256 輸出摘要是256 bit
SHA-384 輸出摘要是384 bit
SHA-512 輸出摘要是512 bit
SHA-1 算法原理 ：分段運算：512 bits ，雜湊值長度：160 bits 渐溶，初始向量：160 bits

• 6-3 Hash函數(shù)的攻擊

一辉浦、生日悖論
生日悖論：在一個會場參加會議的人中，找一個與某人生日相同的概率超過0.5時茎辐，所需參會人員為183人宪郊。但要問使參會人員中至少有兩個同日生的概率超過0.5的參會人數(shù)僅為23人。
二拖陆、對hash函數(shù)的生日攻擊
給定一個散列函數(shù) h 的輸出長度為 n 位弛槐，共有 2n 個可能的散列值輸出，找 x依啰、y 滿足H(x)=H(y)乎串，則嘗試多少個報文可以找到一對（假設散列值為n比特）
顯然，最多嘗試2n＋1個報文速警，必有一對沖突灌闺。
其實，遠在到達2n＋1之前坏瞄，很可能早就找到了桂对。
如果只要達到一定的概率(如1/2)，約需嘗試多少個不同報文鸠匀？答案：2n/2

• 6-4 消息認證

一蕉斜、消息認證碼
消息認證碼 (MAC) 或報文認證碼，是用于提供數(shù)據(jù)原發(fā)認證和數(shù)據(jù)完整性的密碼校驗值。MAC是指消息被一密鑰控制的公開函數(shù)作用后產(chǎn)生的宅此、用作認證符的机错、固定長度的數(shù)值，也稱為密碼校驗和父腕。
二弱匪、基于DES的認證碼（CMAC）
存在的安全問題：如果X的 MAC 為 T=MAC(K,X)，則 X||X^T 的MAC仍然是T璧亮。

三萧诫、基于Hash的認證碼（HMAC）
將某個散列函數(shù)嵌入到消息認證碼的構造過程中。HMAC作為這種構造方法的代表枝嘶，已經(jīng)作為RFC 2104公布帘饶，并在 IPSec 和其他網(wǎng)絡協(xié)議中得到應用。

七群扶、公鑰密碼體制

• 7-1 公鑰密碼體制概述

一及刻、公鑰密碼體制的提出
1、密鑰管理的困難性問題
傳統(tǒng)密鑰管理兩兩分別用一對密鑰時竞阐，n個用戶需要n(n-1)/2個密鑰缴饭，當用戶量增大時密鑰空間急劇增大。
2骆莹、系統(tǒng)的開放性問題
對稱密碼體制的密鑰分發(fā)方法要求密鑰共享各方互相信任茴扁，因此它不能解決陌生人間的密鑰傳遞問題
3、數(shù)字簽名問題
對稱加密算法難以實現(xiàn)抗抵賴的安全需求汪疮。
二峭火、公鑰加密體制的思想
1、公鑰密碼智嚷，也稱非對稱密碼（或雙鑰密碼體制）卖丸。每一個用戶都分別擁有兩個密鑰：加密密鑰（公開）、解密密鑰（私有）盏道。由加密密鑰得到解密密鑰在計算上是不可行的稍浆。
公鑰密碼可以這樣理解：任何人都可以把鎖關上，但只有有鑰匙的人才能把鎖打開猜嘱。而知道關鎖的知識卻無助于開鎖衅枫。
2、陷門單向函數(shù) f 把非對稱密碼這個概念變成了可實行的密碼系統(tǒng)朗伶。
① f 定義域中的任意元素 x, f(x) 的計算是容易的弦撩。
② y=f (x) 中的 y 要計算 x 時，若知道設計 f 時結合進去的某種信息（陷門）论皆，則容易計算益楼；若不知道該信息猾漫，則難以計算。

三感凤、公鑰密碼體制的應用
1悯周、機密性的實現(xiàn)
發(fā)送方用接收方的公鑰加密消息，接收方用自己的私鑰來解密陪竿。
2禽翼、數(shù)字簽名
發(fā)送方用自己的私鑰來簽名消息，接收方通過發(fā)送方對應的公鑰來鑒別消息族跛，且發(fā)送方不能對自己的簽名進行否認闰挡。
3、密鑰分發(fā)和協(xié)商
發(fā)送方和接收方基于公鑰密碼系統(tǒng)容易實現(xiàn)在公開信道上大規(guī)模的密鑰分發(fā)和協(xié)商庸蔼。

公鑰密碼體制認證框圖

• 7-2 RSA公鑰加密體制

RSA方案是被最廣泛接受并實現(xiàn)的公開密鑰密碼算法，目前已成為公鑰密碼的國際標準贮匕。該算法的數(shù)學基礎是歐拉定理姐仅，其安全性基于大整數(shù)因子分解的困難性。
一刻盐、RSA密鑰生成算法
1掏膏、選擇兩個大素數(shù) p、q敦锌，需要保密
2馒疹、計算 n = p×q，φ(n) = (p-1)×(q-1)
3乙墙、選擇 e颖变，滿足 (φ(n), e) =1，1<e<φ(n)
4听想、計算 d腥刹，滿足 d×e ≡ 1mod φ(n)
得到：公鑰為 {e,n} 、私鑰為 t1rt3z3
二汉买、RSA加解密算法
加密用公鑰衔峰，明文：M<n，密文：C = M^e (mod n)
解密用私鑰蛙粘，密文：C垫卤，明文：M = C^d (mod n)
三、RSA公鑰密碼安全性
1出牧、為什么要保密 p穴肘、q
知道了 n 的因子分解，就可以算出 φ(n)舔痕。也就可以利用輾轉相除法梢褐，根據(jù) ed ≡ 1 mod φ(n)旺遮，由e求出d。
2盈咳、形如 p=2p1+1（p1也是素數(shù)）的素數(shù)耿眉，通常稱為安全素數(shù)。
3鱼响、|q – p| 必須要大鸣剪。
4、不同用戶不可共享模n（共模攻擊）
5丈积、私鑰e一般取3或65537（即2^16+1）碉输，這兩個數(shù)的二進制表示中只有兩個1。
e=3 時亏娜，加密只需要一次模乘法和一次模平方职辅；
e=65537 時，加密只需要16次模平方和一次模乘法唬滑。
這使得加密非掣嫠簦快。 2^16+1優(yōu)于3之處在于能夠抵抗對RSA公鑰密碼的低指數(shù)攻擊晶密，因為同樣的消息不可能發(fā)給65537個接收者擒悬。
6、e 和 d 也有些要求稻艰，如e不可太小懂牧，否則不安全。
7尊勿、不同用戶選用的素數(shù)不能相同僧凤。
8、私鑰d一旦泄露元扔，就要更換公鑰n拼弃。
9、按照攻擊者占有資源的不同摇展，分為：選擇明文攻擊者 CPA吻氧、選擇密文攻擊者 CCA1、適應性選擇密文攻擊者 CCA2咏连。
10盯孙、RSA算法滿足的性質：(m1×m2)^e mod n= (m1^e×m2e) mod n
四、本原根
1祟滴、至少有一個 m 滿足 a^m ≡ 1 mod n振惰，且(a,n)=1。稱滿足方程的最小正整數(shù)m為模n下a的階垄懂。
如果 a 的階 m＝φ(n) 骑晶，則稱 a 為 n 的本原根痛垛。
2、只有以下形式的整數(shù)才有本原元：2桶蛔、4匙头、p^a、2pa（a≥1仔雷，p為奇素數(shù)）蹂析。

• 7-3 ElGamal公鑰加密體制

一、ElGamal密鑰生成算法
選取大素數(shù) p碟婆，g∈Zp* 是一個生成元电抚。p、g 作為系統(tǒng)參數(shù)所有用戶共享竖共。每個用戶都隨機挑選整數(shù) x（2≤ x ≤ p-2）蝙叛，并計算 y= g^x(mod p)。(p,g,y) 作為用戶的公鑰公给，x 作為用戶的密鑰借帘。
二、ElGamal加解密算法
1妓布、加密
① 用戶A先把明文 M 編碼為一個整數(shù) m（0≤m≤p-1）
② 用戶A挑選一個秘密隨機數(shù) r ( 2≤ r ≤ p-2 )姻蚓，并計算 c1＝ g^r (mod p)宋梧、c2 ＝ m y^r (mod p)匣沼。y 是用戶B的公鑰，用戶A把 (c1,c2) 作為密文傳送給用戶B捂龄。
2释涛、解密
用戶B接收到密文 (c1,c2) 后，做解密計算 m=c2(c1^x)-1 (mod p)
三倦沧、EIGamal公鑰密碼安全性
同RSA的處理一樣唇撬，假設適應性選擇密文的攻擊者獲得了消息 m 的密文 (c1,c2)。攻擊者隨機選擇r'展融、m'窖认，并計算 c1'＝ c1g^r' (mod p)、c2' ＝ m'c2y^r' (mod p)
攻擊者將構造的新密文 (c1'告希，c2') 送解密機扑浸，返回明文 m m' (mod p)，從而容易得到密文 c 的明文 m燕偶。
兩個基本算法（basic RSA喝噪、basic Elgamal）不安全，因為存在這種同態(tài)的性質指么。

• 7-4 橢圓曲線公鑰加密體制

ECC的安全性基于橢圓曲線離散對數(shù)問題的難解性酝惧。與基于有限域上的離散對數(shù)問題的公鑰密碼體制相比榴鼎，橢圓曲線密碼體制主要有以下兩個方面的優(yōu)點。
1晚唇、密鑰長度小
到目前為止巫财，ECC沒有亞指數(shù)攻擊，在實現(xiàn)相同的安全級別的條件下缺亮，ECC所需要的密鑰長度遠小于后者翁涤。
2、算法性能好
由于密鑰長度小很多萌踱，因此減少了處理開銷葵礼，具有存儲效率、計算效率和通信帶寬的節(jié)約等方面的優(yōu)勢并鸵。

八鸳粉、數(shù)字簽名

8-1 基本概念

數(shù)字簽名是認證的重要工具。
一园担、為什么需要數(shù)字簽名
報文認證用以保護雙方之間的數(shù)據(jù)交換不被第三方侵犯届谈；但它并不保證雙方自身的相互欺騙。
假定A發(fā)送一個認證的信息給B弯汰，雙方之間的爭議可能有多種形式：
1艰山、B偽造一個不同的消息，但聲稱是從A收到的咏闪。
2曙搬、A可以否認發(fā)過該消息，B無法證明A確實發(fā)了該消息鸽嫂。
二纵装、數(shù)字簽名滿足的條件
1、簽名者事后不能否認或抵賴自己的簽名据某。
2橡娄、其他任何人均不能偽造簽名，也不能對信息進行篡改癣籽、偽造挽唉、冒充。
3筷狼、若當事雙方對簽名真?zhèn)伟l(fā)生爭執(zhí)瓶籽，能在公正的仲裁者面前驗證簽名來確定真?zhèn)巍?br> 三、數(shù)字簽名方案的描述
一個數(shù)字簽名方案由兩部分組成：帶有陷門的數(shù)字簽名算法桑逝、驗證算法棘劣。
設M是消息的有限集合，S是簽名的有限集合楞遏，K是密鑰的有限集合茬暇。
則數(shù)字簽名算法是一個映射：sig：M×K→S首昔，s＝sigk(m)。
驗證算法也是一個映射：

五元組 {M糙俗，S勒奇，K，sig巧骚，ver} 就稱為一個簽名算法赊颠。
兩類數(shù)字簽名函數(shù)
1、直接數(shù)字簽名
指數(shù)字簽名的執(zhí)行過程只有通信雙方參與劈彪。雙方有共享的秘密密鑰竣蹦，或接收方知道發(fā)送方的公開密鑰。
缺點：方案的有效性依賴于發(fā)送方密鑰的安全性沧奴。
2痘括、具有仲裁的數(shù)字簽名
指在通信雙方的基礎上引入了第三方仲裁者參與。 所有發(fā)送方X到接收方Y的簽名消息首先送到仲裁者A滔吠，A將消息及其簽名進行一系列測試纲菌，以檢查其來源和內(nèi)容，然后將消息疮绷、日期翰舌、已被仲裁者驗證通過的指示一起發(fā)給Y。
要求：參與者必須極大地相信仲裁機制工作正常冬骚。

8-2 RSA 數(shù)字簽名方案

一椅贱、密鑰的生成
公鑰 Pk={e,n}，私鑰 Sk={d,p,q}唉韭。
二夜涕、簽名過程（用d,n）
用戶A對消息 M∈Zn 進行簽名犯犁，計算 S=Sig(H(M))=H(M)^d (mod n)
將S附在消息M后作為用戶對消息M的簽名属愤。
三、驗證過程（用e,n）
給定 (M,S)酸役，Ver(M,S) 為真住诸，當且僅當 H(M)=S^e (mod n)成立。

8-3 Elgamal 數(shù)字簽名方案

一涣澡、系統(tǒng)初始化過程
同加密算法贱呐，用來設置系統(tǒng)公共參數(shù)和用戶的密鑰。
公鑰為（p入桂，g奄薇，y），私鑰為（x：1≤x＜p-1 ）抗愁，其中有 y=gxmod p
二馁蒂、簽名過程
1呵晚、選擇隨機數(shù) k∈Zp*，且k與p-1互素沫屡；
2饵隙、首先計算消息 M 的哈希值 H(M)，然后計算:
r = g^k mod p沮脖，s = (H(M)－xr) k^(-1) mod (p-1) 金矛。
3、將 (r,s) 作為消息 M 的數(shù)字簽名勺届，與M一起發(fā)送給接收方驶俊。
三、驗證簽名過程
接收方收到 M 與其簽名 (r,s) 后：
1免姿、首先計算消息 M 的哈希值 H(M)废睦。
2、驗證 (y^r)(rs)＝g^H(M) mod p养泡。成立為有效嗜湃，否則為偽造。