Kriptoloji Ders 4

Fermat’s Little Theorem

p asalsa ve a ile p aralarında asalsa

p~asaldır
\\ gcd(a,p)=1
\\\Downarrow
\\ a^{p-1}\equiv 1(mod~p)

\begin{align*}
29^{1000}(mod~37) &\equiv1\\
29^{36*27+28}(mod~37)&=\\
29^{36*27}*29^{28}(mod~37)&=\\
1*29^{28}(mod~37)&=
\end{align*}

Euler Fonksiyonu

In number theory, Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. It is written using the Greek letter phi as {\displaystyle \varphi (n)} or {\displaystyle \phi (n)}, and may also be called Euler’s phi function. In other words, it is the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) is equal to 1.^[2][3] The integers k of this form are sometimes referred to as totatives of n.

\varphi(12)=3*2^2\rightarrow 12*(1-\frac{1}{3})*(1-\frac{1}{2})=4

gcd(9,5)=1\\
\Downarrow\\
\varphi(45)=\varphi(9*5)=\varphi(9)*\varphi(5)

Euler-Fermat Teoremi

gcd(a,m)=1\Rightarrow a^{\varphi(m)}\equiv 1(mod~m)

m\rightarrow asal \Rightarrow \varphi(m)=m-1\\
a^{m-1}\equiv 1(mod~m)

Örnek:

(331)^{51}(mod~49) \equiv ~?\\
gcd(331,49)=1\\~~\\
(331)^{\varphi(49)} \equiv 1(mod~49)\\
\varphi(49)=\varphi(7^2)=7^2-7=42\\
(331)^{42} \equiv 1(mod~49)\\~~\\
(331)^{51}=(331)^{42}*(331)^{9}\\=1*(331)^{9}(mod~49) \equiv 8

Cryptosystem 

In cryptography, a cryptosystem is a suite of cryptographic algorithms needed to implement a particular security service, such as confidentiality (encryption).

Typically, a cryptosystem consists of three algorithms: one for key generation, one for encryption, and one for decryption. The term cipher (sometimes cypher) is often used to refer to a pair of algorithms, one for encryption and one for decryption. Therefore, the term cryptosystem is most often used when the key generation algorithm is important. For this reason, the term cryptosystem is commonly used to refer to public key techniques; however both “cipher” and “cryptosystem” are used for symmetric key techniques.

Formal definition

Mathematically, a cryptosystem or encryption scheme can be defined as a tuple  {\displaystyle ({\mathcal {P}},{\mathcal {C}},{\mathcal {K}},{\mathcal {E}},{\mathcal {D}})}  with the following properties.

1. \mathcal{P}  is a set called the “plaintext space”. Its elements are called plaintexts.
2. \mathcal {C}  is a set called the “ciphertext space”. Its elements are called ciphertexts.
3. \mathcal {K}  is a set called the “key space”. Its elements are called keys.
4. {\displaystyle {\mathcal {E}}=\{E_{k}:k\in {\mathcal {K}}\}}   is a set of functions  {\displaystyle E_{k}:{\mathcal {P}}\rightarrow {\mathcal {C}}}  . Its elements are called “encryption functions”.
5. {\displaystyle {\mathcal {D}}=\{D_{k}:k\in {\mathcal {K}}\}}   is a set of functions   {\displaystyle D_{k}:{\mathcal {C}}\rightarrow {\mathcal {P}}}  . Its elements are called “decryption functions”.

For each  {\displaystyle e\in {\mathcal {K}}}  , there is  {\displaystyle d\in {\mathcal {K}}}   such that  {\displaystyle D_{d}(E_{e}(p))=p}   for all  {\displaystyle p\in {\mathcal {P}}}  .

Note; typically this definition is modified in order to distinguish an encryption scheme as being either a symmetric-key or public-key type of cryptosystem.