4.6 Cryptography

Question 1

Encryption:

Answer 1

The process of making a message secret.

Question 2

Caesar cipher:

Answer 2

To express Caesar’s encryption process mathematically, first replace each letter by an element of Z26, that is, an integer from 0 to 25 equal to one less than its position in the alphabet. For
example, replace A by 0, K by 10, and Z by 25. Caesar’s encryption method can be represented
by the function f that assigns to the nonnegative integer p, p ≤ 25, the integer f(p) in the set
{0, 1, 2, … , 25} with
f( p) = ( p + 3) mod 26.
In the encrypted version of the message, the letter represented by p is replaced with the letter
represented by ( p + 3) mod 26.

Question 3

Decryption:

Answer 3

The process of determining the original message from the encrypted message is called
decryption.

Question 4

Decrypt Caesar Cipher:

Answer 4

To recover the original message from a secret message encrypted by the Caesar cipher, the
function f −1, the inverse of f , is used. Note that the function f −1 sends an integer p from Z26,
to f −1(p) = (p − 3) mod 26. In other words, to find the original message, each letter is shifted
back three letters in the alphabet, with the first three letters sent to the last three letters of the
alphabet.

Question 5

Shift Cipher:

Whats key?

Answer 5

Generalized Caesar Cipher.
f(p) = (p + k) mod 26.
Such a cipher is called a shift cipher. Note that decryption can be carried out using
f −1
(p) = (p − k) mod 26.
Here the integer k is called a key.

Question 6

Affine cipher:

Answer 6

Shift cipher with slightly enhanced security.
f( p) = (ap + b) mod 26,
where a and b are integers, chosen so that f is a bijection. (The function f(p) = (ap + b) mod 26
is a bijection if and only if gcd(a, 26) = 1.) Such a mapping is called an affine transformation,
and the resulting cipher is called an affine cipher.

Question 7

How to decrypt messages encrypted using an affine cipher?

Answer 7

Suppose
that c = (ap + b) mod 26 with gcd(a, 26) = 1. To decrypt we need to show how to express p in
terms of c. To do this, we apply the encrypting congruence c ≡ ap + b (mod 26), and solve it
for p. To do this, we first subtract b from both sides, to obtain c − b ≡ ap (mod 26). Because
gcd(a, 26) = 1, we know that there is an inverse a of a modulo 26. Multiplying both sides of
the last equation by a gives us a(c − b) ≡ aap (mod 26). Because aa ≡ 1 (mod 26), this tells
us that p ≡ a(c − b) (mod 26). This determines p because p belongs to Z26

Question 8

CRYPTANALYSIS:

Answer 8

The process of recovering plaintext from ciphertext without knowledge
of both the encryption method and the key is known as cryptanalysis or breaking codes.

Question 9

Cryptanalysis if u know shift cipher was used:

Answer 9

One way: we can try to recover the message by shifting all characters of the ciphertext by each
of the 26 possible shifts (including a shift of zero characters). One of these is guaranteed to be
the plaintext.

Other way:
The main tool for cryptanalyzing cipher- text encrypted using a shift cipher is the count of the frequency of letters in the ciphertext.
The nine most common letters in English text and their approximate relative frequencies are E 13%,
T 9%, A 8%, O 8%, I 7%, N 7%, S 7%, H 6%, and R 6%.

First hythesize that most frequent letter is E, if it makes sense then true otherwise go for T.

Question 10

character or

monoalphabetic ciphers.

Answer 10

Shift ciphers and affine ciphers proceed by replacing each letter of the alphabet by another letter in the alphabet. Because of this, these ciphers are called character or monoalphabetic ciphers.
Encryption methods of this kind are vulnerable to attacks based on
the analysis of letter frequency in the ciphertext.

Question 11

Block Ciphers:

Answer 11

We can make it harder
to successfully attack ciphertext by replacing blocks of letters with other blocks of letters instead of replacing individual characters with individual characters; such ciphers are called block
ciphers.

Question 12

Transposition Cipher:

Encryption and decrption:

Answer 12

As a key we use a permutation 𝜎 of the set {1, 2, … , m} for some positive integer m, that is, a
one-to-one function from {1, 2, … , m} to itself.
To encrypt a message we first split its letters
into blocks of size m. (If the number of letters in the message is not divisible by m we add
some random letters at the end to fill out the final block.)
We encrypt the block p1p2 … pm as
c1c2 … cm = p𝜎(1)p𝜎(2) … , p𝜎(m).
To decrypt a ciphertext block c1c2 … cm, we transpose its letters using the permutation 𝜎−1, the inverse of 𝜎.

Example 6 to understand.

Question 13

CryptoSystem:

Answer 13

A cryptosystem is a five-tuple (P, C, K, E, D), where P is the set of plaintext strings,
C is the set of ciphertext strings,
K is the keyspace (the set of all possible keys),
E is the set of encryption functions, and
D is the set of decryption functions.
We denote by Ek the encryption
function in E corresponding to the key k and Dk the decryption function in D that decrypts
ciphertext that was encrypted using Ek, that is, Dk(Ek(p)) = p, for all plaintext strings p.

Question 14

Describe the family of shift ciphers as a cryptosytem.

Answer 14

To apply the definition of a cryptosystem to shift ciphers, we assume that our messages are already integers,:
that is, elements of Z26. That is, we assume that the translation between letters and integers is
outside of the cryptosystem. Consequently, both the set of plaintext strings  and the set of
ciphertext strings  are the set of strings of elements of Z26. The set of keys  is the set of
possible shifts, so  = Z26. The set  consists of functions of the form Ek(p) = (p + k) mod 26,
and the set  of decryption functions is the same as the set of encrypting functions where
Dk(p) = (p − k) mod 26.

Question 15

Private key cryptosystems :

Answer 15

All classical ciphers, including shift ciphers and affine ciphers, are examples of private key
cryptosystems. In a private key cryptosystem, once you know an encryption key, you can
quickly find the decryption key. So, knowing how to encrypt messages using a particular key
allows you to decrypt messages that were encrypted using this key.

• When a private key cryptosystem is used, two parties who wish to communicate in secret
  must share a secret key. Because anyone who knows this key can both encrypt and decrypt messages, two people who want to communicate securely need to securely exchange this key

Question 16

Working with private key cryptosystems and enhancing it security:

Answer 16

US government standard for private key cryptography, the Advanced
Encryption Standard (AES), is extremely complex and is considered to be highly resistant to
cryptanalysis. (See [St06] for details on AES and other modern private key cryptosystems.)
AES is widely used in government and commercial communications. However, it still shares
the property that for secure communications keys be shared. Furthermore, for extra security, a
new key is used for each communication session between two parties, which requires a method
for generating keys and securely sharing them.

Question 17

Public Key Cryptosystems:

Answer 17

To avoid the need for keys to be shared by every pair of parties that wish to communicate securely, in the 1970s cryptologists introduced the concept of public key cryptosystems.
When such cryptosystems are used, knowing how to send an encrypted message does not help
decrypt messages. In such a system, everyone can have a publicly known encryption key. Only
the decryption keys are kept secret, and only the intended recipient of a message can decrypt
it, because, as far as it is currently known, knowledge of the encryption key does not let someone recover the plaintext message without an extraordinary amount of work (such as billions of
years of computer time).

Question 18

Any flaw of public key cryptosystem:

Answer 18

Although public key cryptography has the advantage that two parties who wish to communicate securely do not need to exchange keys, it has the disadvantage that encryption and
decryption can be extremely time-consuming.

Question 19

RSA cryptosystem:

Answer 19

Each individual has an encryption key (n, e), where n = pq, modulus is the product of two large primes p and q, say with 300 digits each, and an exponent
e that is relatively prime to (p − 1)(q − 1).

To produce a usable key, two large primes must be
found. This can be done quickly on a computer using probabilistic primality tests.
However, the product of these primes n = pq, with approximately 600
digits, cannot, so far, be factored in a reasonable length of time. As we
will see, this is an important reason why decryption cannot be done quickly without a separate decryption key.

Question 20

As computing power is increased what happens to RSA?

Answer 20

With the steady increase of the speed of computers, the recommended size of the
primes p and q used to produce a RSA public key has increased. But the larger n is, the slower
RSA encryption and decryption become. When considering this tradeoff, the number of years
a message needs to be remain secret is important. A more important consideration is that the
development of quantum computing threatens the security of the RSA cryptosystem, because
factorization algorithms have been developed for quantum computers that could then be used to
quickly factor large primes. So, once quantum computing becomes practical, perhaps in the next
20 to 30 years, other public key cryptosystems that cannot be broken using quantum computing
will need to be used.

Question 21

RSA encyption:

Answer 21

To encrypt messages using a particular key (n, e), we first translate a plaintext message M
into sequences of 2 digit integers. Include initial zero for single digits like A : 00.
Then, we concatenate these two-digit numbers into strings of digits. Next, we divide this string into equally sized blocks of 2N digits, where 2N is the largest
even number such that the number 2525… 25 with 2N digits does not exceed n. (When necessary, we pad the plaintext message with dummy Xs to make the last block the same size as all
other blocks.)
After these steps, we have translated the plaintext message M into a sequence of integers
m1, m2, … , mk for some integer k. Encryption proceeds by transforming each block mi to a
ciphertext block ci.
This is done using the function
c = m^e mod n. (Use fast modular func, as in 4.2 )

RSA is a block Cipher.

Question 22

RSA Decryption

TOUGH TO WRAP MY HEAD AROUND IT!!!!!UGHH

Answer 22

key d, :an inverse of e modulo (p − 1)(q − 1), is known.
then t de = 1 + k(p − 1)(q − 1)
c^d ≡ (m^e)^d = m^(de) = m^(1+k(p−1)(q−1)) (mod n).

By Fermat’s little theorem [assuming that gcd(m, p) = gcd(m, q) = 1, which holds except in rare
cases, which we cover in Exercise 28], it follows that mp−1 ≡ 1 (mod p) and mq−1 ≡ 1 (mod q).
Consequently,
c^d ≡ m ⋅ (m^(p−1))^(k(q−1)) ≡ m ⋅ 1 = m (mod p)
and
c^d ≡ m ⋅ (m^(q−1))^(k(p−1)) ≡ m ⋅ 1 = m (mod q).
Because gcd(p, q) = 1, it follows by the Chinese remainder theorem that
c^d ≡ m (mod pq).

so m ≡ c^d (mod n), fast modular exponentiation to get m ( block).

Question 23

RSA as a Public Key System

Answer 23

that para how it works, factorization is hard, finding inverse from Bezout’s coef.
Application:
RSA, can be used to distribute private keys to pairs of individuals when they wish to communicate. These people then use a private key
system for the encryption and decryption of messages.

Question 24

Cryptographic Protocols

Answer 24

Exchanges of messages carried out by two or more parties to achieve a particular security goal.

Question 25

Key Exchange:

Protocol:

Answer 25

Diffie-Hellman key agreement protocol.
Protocol that two parties can use to exchange a secret
key over an insecure communications channel without having shared any information in the
past.

Question 26

Steps of Diffe-Hellman key agreement protocol:

and its analysis:

Answer 26

Suppose that Alice and Bob want to share a common key. The protocol follows these steps,
where the computations are done in Zp.
(1) Alice and Bob agree to use a prime p and a primitive root a of p.
(2) Alice chooses a secret integer k1 and sends
a^k1 mod p to Bob.
(3) Bob chooses a secret integer k2 and sends
a^k2 mod p to Alice.
(4) Alice computes (a^k2 )^k1 mod p.
(5) Bob computes (a^k1 )^k2 mod p.
At the end of this protocol, Alice and Bob have computed their shared key, namely,
(a^k2 )^k1 mod p = (a^k1 )^k2 mod p

Solving Discrete Algo is hard we know, With the computing power available now, this system is considered unbreakable when p has more than 300 decimal digits and k1 and k2 have more than 100 decimal
digits each.

Question 27

DIGITAL SIGNATURES:

DONT UNDERSTAND THIS AT ALL!!

Answer 27

To be sure of sender.
Suppose that Alice’s RSA public key is (n, e) and her private key is d. Alice encrypts a
plaintext message x using the encryption function E(n,e)(x) = x^e mod n. She decrypts a ciphertext
message y using the decryption function
D(n,e) = x^d mod n.
She wants to send M.
she translates the letters into their numerical equivalents and splits the resulting
string into blocks m1, m2, … , mk such that each block is the same size, which is as large as
possible so that 0 ≤ mi ≤ n for i = 1, 2, …, k. She then applies her decryption function D(n,e) to
each block, obtaining Dn,e(mi
), i = 1, 2, … , k. She sends the result to all intended recipients of
the message.

Question 28

RSA is Partially Homomorphic :

Answer 28

Skipped for now, can’t understand need practise with modular arithmetic first.
RSA is multiplicatively holomorphic not additively.

Question 29

a fully homomorphic cryptosystem:

Answer 29

the question was proposed
whether there was a cryptosystem that allowed arbitrary computations to be run on encrypted
data that would produce the encryption of the unencrypted output produced by this unencrypted
input. For such a cryptosystem, it would not be necessary to decrypt input data because the
program could be run on a remote system without disclosing either the input or the output.

In 2009, Craig Gentry described the first fully homomorphic cryptosystem, based on what
is known as lattice-based cryptography.