Nomad Note
Someone's Intermediate Representation
Archives47
Tags10
VE475 Cryptography Note 1
Posted on 2019-05-21 In Course Note Disqus:
All info comes from Manuel's slides on Lecture 1.
Five Main Types of Attacks
Ciphertext only: Attacker has only a copy of the ciphertext
Known Plaintext Attack: Attacker has a copy of ciphertext and corresponding plaintext
Chosen Plaintext Attack: Attacker chooses the plaintext to be encrypted.
Chosen Ciphertext Attack: Attacker chooses the ciphertext to be decrypted.
Chosen Plaintext and Ciphertext Attack: Attacker chooses any plaintext to be encrypted or ciphertext to be decrypted.
OTP (One Time Pad)
By XORing message and key, it is almost not possible to decrypt the ciphertext.
Consider the previous attack methods, the breaking results turn out to be
Ciphertext only: all messages of same length can have possibility.
KPA/CCA/CPA: only reveal part of the key used during the attack. (Since key means a set of key for XOR)
Hill Cipher
First we should have a look at the inverse of matrix of $m\times m$ size, consider $m=2$ or $3$:
A\equiv\begin{pmatrix}a&b\\c&d\end{pmatrix}, A^{-1}\equiv\dfrac{1}{\mid A\mid}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}\\
A\equiv\begin{pmatrix}a_{11}&a_{12}&a_{13}\\a_{21}&a_{22}&a_{23}\\a_{31}&a_{32}&a_{33}\end{pmatrix},A^{-1}\equiv\dfrac{1}{\mid A\mid}\begin{pmatrix}\begin{vmatrix}a_{22}&a_{23}\\a_{32}&a_{33}\end{vmatrix}&\begin{vmatrix}a_{13}&a_{12}\\a_{33}&a_{32}\end{vmatrix}&\begin{vmatrix}a_{12}&a_{13}\\a_{22}&a_{23}\end{vmatrix}\\\begin{vmatrix}a_{23}&a_{21}\\a_{33}&a_{31}\end{vmatrix}&\begin{vmatrix}a_{11}&a_{13}\\a_{31}&a_{33}\end{vmatrix}&\begin{vmatrix}a_{13}&a_{11}\\a_{23}&a_{21}\end{vmatrix}\\\begin{vmatrix}a_{21}&a_{22}\\a_{31}&a_{32}\end{vmatrix}&\begin{vmatrix}a_{12}&a_{11}\\a_{32}&a_{31}\end{vmatrix}&\begin{vmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{vmatrix}\end{pmatrix}
Then by Cramer's Rule that: Let $A$ be an $m\times m$ matrix, then $\text{Adj}(A)\cdot A=\text{det}(A)I_{m}$, where $\text{Adj}(A)$ donates the adjugate of $A$.
Thus, $A$ must be invertible to get $A^{-1}$ and $\text{Adj}(A)$. ($\text{Adj}(A)=\begin{vmatrix}A\end{vmatrix}A^{-1}$)
Consider the matrix inversion on mod $n$, then by $A\cdot A^{-1}\equiv I_{m}\text{ mod }26$, we can see that $\text{det}(A)$ must be invertible modulo $n$.
Take $A=\begin{pmatrix}1&1&1\\1&2&3\\1&4&9\end{pmatrix}\text{ mod }11$ as example. We can see that $A^{-1}=\dfrac{1}{2}\begin{pmatrix}6&-5&1\\-6&8&-2\\2&-3&1\end{pmatrix}\text{ mod }11$. $6$ is invertible modulo $11$ for $2$, then $A^{-1}=\begin{pmatrix}3&3&6\\8&4&10\\1&4&6\end{pmatrix}\text{ mod }11$.
The key for Hill cipher requires $n\times n$ matrix $K\text{ mod }26$, with $\text{gcd}(\text{det}(K),n)=1$.
Symmetric and Asymmetric Key
Symmetric scheme use same key for both encrypt and decrypt. Thus the key management problem arises when user number increases: $n$ users means $O(n^2)$ keys.
Asymmetric scheme creates a pair of public and private key. Encrypt with public key and decrypt with private key.
Double Encryption
Consider symmetric encryption using function $f$ and key $k$:
Simple encryption: $c=f_{k}(m)$
Double encryption: $c=f_{k_2}(f_{k_1}(m))$
Decryption: $m = f_{k_1}^{-1}(f_{k_2}^{-1}(c))$
Assume the KPA setup, then we can setup meet in the middle attack.
$\forall k\in\lbrace\text{Key}\rbrace$, compute and store the ciphertexts $c_i=f_{k_i}(m)$.
Compute $m_i=f_{k_i}^{-1}(c)$ and find the matching $c_i$.
Recover the $k_1$ and $k_2$.
Thus double encryption do not guarantee a multiple instruction complexity, it can only guarantees a plus instruction complexity. (Not $I_1\times I_2$ but $I_1 +I_2$)
Zero Knowledge Proof
+--------------------+--------------------+
|                    |                    |
|                    ?                    |
|           +--------+--------+           |
|           |                 |           |
|           +-----------------+           |
|     L           +-----+           R     |
|                 | Bob |                 |
+-------------+   +-----+   +-------------+
|             |
|             |  +-------+
|             |  | Alice |
If Bob wants to prove he knows a secret path without revealing it, what should he do?
The strategy is that:
Alice hides while Bob go L or R.
Alice randomly asks Bob to exit on L or R.
If Bob is on the wrong side he uses the secret path or he returns.
Repeat previous steps many times.
Graph Isomorphism and Hamiltonian Circuit
Graph Isomorphism is defined on $G_1=(V_1,E_2)$ and $G_2=(V_2,E_2)$ two simple graphs.
If there exists a bijection function $\varphi:V_1\to V_2$ such that the induced map $\varphi_\ast:E_1\to E_2, (a,b)\mapsto(\varphi(a),\varphi(b))$ is bijective. Such $\varphi$ is a graph isomorphism.
Graph isomorphism is not known to be $NPC$ problem, but the best known algorithm has exponential complexity.
Hamilton circuit in $G$ is a simple circuit that passes through every vertex in $G$ exactly once. It is proven to be $NPC$ and best known algorithm has exponential complexity.
In this scenario, we can set the condition as
A graph $G$ Bob's graph $G$
Hamiltonian Circuit in $G$
The process goes like:
Bob generates $H\cong G$ and commits it.
Alice randomly asks for either isomorphism map or Hamiltonian circuit in $H$.
Bob show the required result.
The procedure is not related to the security level like $2^{128}$ stuff.
# Cryptography
PFPL Chapter 20 System FPC of Recursive Types
1. Five Main Types of Attacks
2. OTP (One Time Pad)
3. Hill Cipher
4. Symmetric and Asymmetric Key
5. Double Encryption
6. Zero Knowledge Proof
6.1. Graph Isomorphism and Hamiltonian Circuit
AnthonySu
SWE in Algorand, 24 yo, used to be a student. He loves Crypto, PL, Systems and Good Stories.
GitHub E-Mail School Mail RSS
Patrick Yao
Jason Qian
John Cai
© 2017 – 2022 AnthonySu