VE475 Cryptography Note 1

Posted on In 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
+--------------------+--------------------+
|                    |                    |
|                    ?                    |
|                    |                    |
|           +--------+--------+           |
|           |                 |           |
|           |                 |           |
|           |                 |           |
|           |                 |           |
|           +-----------------+           |
|                                         |
|     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

Bob Alice
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.