---
# System prepended metadata

title: 密碼學補考筆記

---

# 密碼學補考筆記

## 名詞解釋： 

### 完善保密性
答： 密善保密性是指敵手無法根據給定密文得到明文的任何信息。

### 一次性簽名
答： 如果一個簽名方案僅給一則消息簽名時是安全的，那麼稱這一簽名方案為一次性簽名方案，也稱Lamport簽名方案。

### 全域Hash 
答： 利用陷門單向置換來構造在隨機諭示模型下的安全簽名方案，稱這種簽名方案為全域Hash。

### 密文識別
答： 敵手能以超過1/2的概念識別兩個明文對的密文，或識別出給定明文的密文和隨機串。

### 計算DH問題
答： 書P215， 問題6.3。

### 完全攻破
答： 敵手能找到秘密密鑰或私鑰，因此，敵手能通過解密利用給定密鑰加密任意密文。

### 部分破解
答： 敵手能以某一不可忽略的概率解密以前從未見過的密文（無須知道密鑰）。
或者，敵手能夠對於給定的密文，得出明文的一些特定信息。

### 不可否認簽名
答： 不可否認簽名是由Chaum和van Antwerpen 在1989年提出的。不可否認簽名的最主要的一點是沒有簽名者的合作，簽名就不能得到驗證。驗證簽名通過，口令-應答協議來實現。

### 消息認證碼MAC
答： 密碼學中，通信實體雙方使用的一種驗證機制，保證消息數據完整性的一種工具。
安全性依賴於Hash函數，故也稱帶密鑰的Hash函數。消息認識碼的作用在於解決信息的完整性和發送者的正確性。

### 計算安全性
答： 如果破解一個密碼體制需要N個操作，且這個N是一個非常大的數字，則稱這密碼體制是計算安全的。

### 可證明安全性
答： 使用歸約的方式為密碼體制提供安全證據，例如： 給定一個N，且N無法被分解，則稱該密碼體制是可證明安全性的。

### 無條件安全性
答： 即使給出無限的算力也無法攻破的密碼體制，就是無條件安全性的。

## 計算題

### 计算Jacobi的值 (610/987)

我们可以使用以下公式来计算Jacobi的值：
(a/n) = (a/p1)^e1 * (a/p2)^e2 * … * (a/pr)^er
其中，p1, p2, …, pr 是n的所有质因数，e1, e2, …, er 是a模每个质因子的指数。
因此，对于Jacobi(610/987)，我们需要先分解987为质因数的积：
987 = 3^2 * 109
然后，我们可以将610模3和109分别求余：
610 mod 3 = 2
610 mod 109 = 44
接下来，我们需要计算每个质因子对应的指数。由于3不是奇素数，我们可以使用以下公式来计算：
(a/p) = (-1)^((p-1)/2 * (a-1)/2) * (p/a)
因此，
(610/3) = (-1)^(1*1/2) * (2/3) = -1
因为2是一个二次剩余模3，所以(2/3) = 1。
接下来，我们需要计算109的指数。由于109是一个奇素数，我们可以使用以下公式来计算：
(a/p) = a^((p-1)/2) mod p
因此，
(610/109) = 610^((109-1)/2) mod 109
= 610^54 mod 109
= 1
因此，Jacobi(610/987) = Jacobi(610/3)^2 * Jacobi(610/109) = (-1)^2 * 1 = 1。
因此，Jacobi(610/987) = 1。


## 簡答題

### 什麼是RSA問題，為什麼整數分解問題可解相當於RSA問題可解？
答： RSA加密算法是一種依賴於兩個素數P,Q乘積N的非对称加密算法，故當乘積的整數N可分解時，RSA問題就可解了，反之當整數N不可分解時，RSA問題不可解。


