So I have been reading up on my cryptography and I figured I should give out a brief lesson on these three amazing concepts
What are they ?
a) PRG (Pseudo Random Generator)
You probably know the difference between stream and block cipher. One of the main differences between them is key size. Stream ciphers require the key to be of equal length of greater than the plaintext , whereas Block Ciphers take a key smaller than the PT and is then expanded. This is the PRG
Considerations: Stream Ciphers base on Perfect Secrecy whereas Block Ciphers base on Semantic Security
b) PRF (Pseudo Random Function)
Lets share a secret- imagine something- you want to authenticate yourself with me by proving that you know a secret that we both share. Here's a possible option
i) Possible Option 1: PRNGs
We both seed a PRNG with the shared secret, I pick and then send you some random number i.
You then have to prove that you know the secret by responding with the i th random number generated by the PRNG, meaning you will feed the PRNG with that number that I had picked for you then you give the output (so we compare).
Disadvantage: We have to compute i random numbers and we both require state.
ii) Better Option 2: "Random Access"
This is the backbone that drove the birth of PRFs. I give you some random i and you return Fk(i).
This is indistinguishable from a random function. What do I mean? Given any
x1, . . . ,xm, Fk(x1), . . . Fk(xm). No-one will be able to predict the next item in the sequence (summarized like so): Fk(xm+1) for any xm+1
In one line PRF is where F: K * X = Y
c) PRP (Pseudo Random Permutation)
The ideal block cipher is a collection of truly random permutations of the mappings between plaintext and ciphertext. The ideal block cipher is a collection (i.e E = {P1,...P2s}) of random permutations that maps n-bits to n-bits. Encryption is then defined as C = Pk(M) (K is the shared key in {1...,2 to the power of s}) and decryption is then defined as M = P-1k(C).
This is impossible to achieve (as ordering is random) in practice so we use PRPs. But with three rounds of PRF it is then possible to make an invertible block cipher. How so?
Luby-Rackoff definition
The loose definition is listed below.
a) Lets now assume a round Feistel Network and split the block in two L0 and R(remember that the plaintext is split into blocks when it comes to stream ciphers) Refer to the image below to refresh your memory of a Feistel Network
What are they ?
a) PRG (Pseudo Random Generator)
You probably know the difference between stream and block cipher. One of the main differences between them is key size. Stream ciphers require the key to be of equal length of greater than the plaintext , whereas Block Ciphers take a key smaller than the PT and is then expanded. This is the PRG
 |
| The PRG expands the seed |
b) PRF (Pseudo Random Function)
Lets share a secret- imagine something- you want to authenticate yourself with me by proving that you know a secret that we both share. Here's a possible option
i) Possible Option 1: PRNGs
We both seed a PRNG with the shared secret, I pick and then send you some random number i.
You then have to prove that you know the secret by responding with the i th random number generated by the PRNG, meaning you will feed the PRNG with that number that I had picked for you then you give the output (so we compare).
Disadvantage: We have to compute i random numbers and we both require state.
ii) Better Option 2: "Random Access"
This is the backbone that drove the birth of PRFs. I give you some random i and you return Fk(i).
This is indistinguishable from a random function. What do I mean? Given any
x1, . . . ,xm, Fk(x1), . . . Fk(xm). No-one will be able to predict the next item in the sequence (summarized like so): Fk(xm+1) for any xm+1
In one line PRF is where F: K * X = Y
c) PRP (Pseudo Random Permutation)
The ideal block cipher is a collection of truly random permutations of the mappings between plaintext and ciphertext. The ideal block cipher is a collection (i.e E = {P1,...P2s}) of random permutations that maps n-bits to n-bits. Encryption is then defined as C = Pk(M) (K is the shared key in {1...,2 to the power of s}) and decryption is then defined as M = P-1k(C).
This is impossible to achieve (as ordering is random) in practice so we use PRPs. But with three rounds of PRF it is then possible to make an invertible block cipher. How so?
Luby-Rackoff definition
The loose definition is listed below.
a) Lets now assume a round Feistel Network and split the block in two L0 and R(remember that the plaintext is split into blocks when it comes to stream ciphers) Refer to the image below to refresh your memory of a Feistel Network
ENCRYPTION: L1 = R0 and R1 = L0 ⊕ f(R0), where f is a PRF. Cipher text is L2 = R1, R2 = L1
Decryption is the same encryption circuit as shown in image above. Lets say we want to decrypt L3 and R3. Meaning the input to decryption is L2 and R2. So it would be as below:
L3 = R2
R3 = L2 ⊕ f(R2)
Now lets substitute from
L3=L1,
R3=R1⊕f(L1)
Now lets substitute further to get the plain text R3, L3 which is L0, R0 as shown below
L3=R0,
R3=L0 ⊕ f(R0) ⊕ f(R0),
R3=L0
So it does not really matter if f(R0) is reversible or not. And the same holds good for any number of rounds.
In one line PRP is where F: K * X = X
Comments
Post a Comment