題目

1. For each type of the following attacks, list all information and/or encryption/decryption programs the attacker of a cryptosystem can have?

• 102, 106, 107, 109
• 12%

Ciphertext-only attack

• 攻擊者僅有密文。
• 攻擊者有encryption/decryption program

Known-plaintext attack

• 攻擊者有一組以上密文與明文。
• 攻擊者有encryption/decryption program

Chosen-Plaintext Attack

• 攻擊者可將明文轉為密文。
• 攻擊者有encryption/decryption program

Chosen-Ciphertext Attack

• 攻擊者可將密文轉為明文。
• 攻擊者有encryption/decryption program

Kerckhoffs原理

• 『對於一密碼系統的安全性，應假設敵人是知道所使用的方法。』
• 攻擊者有encryption/decryption program

2. Explain the following requirements of information security

• 102, 106, 107, 109
• 12%

Confidentiality(for privacy)

• 機密性，第三者無法破譯

Authentication

• 可認證性，確保為當事人發出

Integrity

*　資料完整性，確定訊息未被竄改

Non-repudiation

• 不可否認性，傳送者無法否認訊息由他送出

3. Explain the following type of security

*　102,106,109
*　12%

unconditional security

• 無條件安全
• 即使截收到無限密文，也無法確定其密鑰

computational security

• 計算上安全
• 破解密文的花費遠遠大於所加密訊息的價值。
• 破解密文所花費的時間遠遠多於該資訊的有效期間

provable security

• 可證明安全
• 該密碼安全性問題為公認困難問題或更難。

storage-bound security

• 對於攻擊者來說此加密問題所需之容量極大

4. Answer the following questions about vigenere cipher

*　102,106,107,109
*　12%

How to encrypt and decrypt vigenere cipher?

Encrypt

• 定義訊息為
  $x=\{x_1,x_2,...,x_m\}\in (Z/26{)}^d$,密鑰為
  $k=\{k_1,k_2,...,k_m\}\in (Z/26{)}^d$
• $E(x)=x+k=(x_1+k_1,x_2+k_2,...,x_d+k_d)mod26$

Decrypt

• 定義密文為
  $y=\{y_1,y_2,...,y_m\}\in (Z/26{)}^d$,密鑰為
  $k=\{k_1,k_2,...,k_m\}\in (Z/26{)}^d$
• $D(y)=y-k=(y_1-k_1,y_2-k_2,...,y_d-k_d)mod26$

What is index of coincidence

• 字串任取兩字母為相同之機率
• $I(x)=\frac{{\mathrm{\Sigma }}_{i=1}^{26}(\genfrac{}{}{0ex}{}{P_i}{2})}{(\genfrac{}{}{0ex}{}{n}{2})}$
• n為字串長度，
  $P_i$為字母在字串中的出現次數

What's the difference between mono-alphabetic cipher and poly-alphabetic cipher

• 在 mono 中同一個字母只會被轉換成一種結果，如所有凱撒密碼 A 都變成 D
• 在 poly 中則可能變成多種結果如 vigenere

How to attack vigenere cipher

1. 將密文切成數個 m 長度的字串
2. 計算各字串的 index of coincidence
3. 若 index of coincidence 接近 0.066 則ｍ為密鑰之長度（或其整數倍)，否則接近 0.038
4. 若為前者則做頻率分析破解密文內容，若為後者則調整 m 長度

5. Answer the following questions about block cipher

*　102,106,107,109
*　12

What's the SPN (Substituition-Permutation network structure)? draw!

• Round
  • 在各輪將處理中密文與key做運算(e.g. 互斥或(xor))
• Substitution 代換
  • 將各輸入字符１對１替換
• Permutation 置換
  • 將輸入重新排列（e.g. 左移右移）
• 進行數輪
• 必須可逆

What's the Feistel Network structure?draw!

• 輸入須為偶數
• 加密
  • 在每輪將右半與
    $(R_i,K_i)$互斥或
    $(XOR)$併當作下一輪的左半。左半則為下一輪的右半
• 解密
  • 同樣的結構，但是i由n到1

Main differences

• SPN s-box必須可逆，來解密。FEISTEL則只需倒序使用 KEY 解密

6. DES Problems

• 102,106,107
• 5~15%

Encrypt and Decrypt

Round Key generation procedure

•  由密鑰 K 產生16 個 48-bit sub-keys
  $K_i,1\le i\le 16$

Not safe? why?

• 56-bit key size 太小, 1999年就能在一內破解解

AES Problems

• 102,106,107,109
• 10 ~15

Encryption

AddRoundKey(S,K[0]);
for(i=1;i<=9;i++)
{
    SubByte(S);
    ShiftRow(S);
    MixColumn(S);
    AddRoundKey(S,K[i]);
}
SubByte(S);
ShiftRow(S);
AddRoundKey(S,K[10]);

Decryption

AddRoundKey(S,K[10]);
InverseShiftRow(S);
InverseSubByte(S);
for(i=9;i>=1;i--)
{
    AddRoundKey(S,K[i]);
    InverseMixColumn(S);
    InverseShiftRow(S);
    InverseSubByte(S);
}
AddRoundKey(S,K[0]);

7. Computation

• 102,106,107,109
• 12~15%

Find an x = 1~10 such that

$2^x=7(mod11)$

• 也可硬算
• $7+11=18$
• $2^{1}mod11=2$
• $2^{2}mod11=4$
• $2^{3}mod11=8$
• $2^{4}mod11=5$
• $2^{5}mod11=10$
• $2^{6}mod11=9$
• $2^1\ast 2^{6}mod11=18-11$
• ans = 7

GCD

gcd(2021,3031)

• gcd(2021,3031) = gcd(2021,1010) = gcd(1,1010)=1

gcd(357,1235)

• gcd(357,1235) = gcd(357,164) = gcd(29,164) = gcd(29,19) = gcd(10,19) = gcd(10,9) = gcd(1,9) = 1

Inverse

• 較難

${3031}^{-1}(mod2021)$

• $3031=1\ast 2021+1010$
• $2021=2\ast 1010+1$
• $1=2021-2\ast 1010=2021-2\ast (3031-2021)=2021\ast 3+3031\ast -2$
• $3031\ast (2021-2)+2021\ast (3-3031)=3031\ast 2019+2021\ast -3028=1$
• Ans:
  $2019$

${357}^{-1}mod1235$

• $1235=3\ast 357+164$,
• $357=2\ast 164+29$,
• $164=5\ast 29+19$,
• $29=1\ast 19+10$,
• $19=1\ast 10+19$,
• $10=1\ast 9+1$
• $1=10-9=10-(19-10)=-19+2\ast 10=-19+2\ast (29-19)=2\ast 29-3\ast 19$
• $=2\ast 29-3\ast (164-5\ast 29)=17\ast 29-3\ast 164$
• $=17\ast (357-2\ast 164)-3\ast 164=17\ast 357-37\ast 164$
• $=17\ast 357-37(1235-3\ast 357)=128\ast 357-37\ast 1235$
• Ans =
  $128$

費馬小定理

$7^{843}mod43$

• $gcd(7,43)=1->7^{42}=1(mod43)$
• $7^{3}mod43=42$
• ans:
  $42$

${1234}^{10}mod11$

• $gcd(1234,11)=1->{1234}^{10}mod11=1$

8. Answer the following

• Block cipher, Stream cipher
  • Block cipher 以一把key以block為單位加密(without memory)
  • Stream cipher key不斷改變一次加密一個byte 或bit(with memory)
• Symmetric, Asymmetric
  • Symmetric Cryptosystems: 其加密鑰=解密鑰，鑰匙是保密的。
  • Asymmetric Cryptosystems:其加密鑰≠解密鑰，且加密鑰為公開鑰(Public Key)而解密鑰為私鑰(Private Key)。

9. asymmetric crypto sign and verify

• Using asymmetric (public-key) cryptosystems, suppose Alice (A) want to sign and encrypt a document to Bob (B), and Bob need to decrypt and verify the document. Alice has her public key KUA and private key KRA, whereas Bob has his public key KUB and private key KRB. Please sketch a flowchart to illustrate the process of using these keys to sign/verify and encrypt/decrypt for Alice and Bob.
  

tags: Introduction to Information Security CSnote