Pseudo Random Linier Congruential (LC) dan Blum Blum Sub Generator (BBSG) serta Stream Cipher

Summary

In this educational video, the topic of stream ciphers and random number generation in cryptography is explored. The video explains key concepts like True Random Number Generators (TRNG) and Pseudo-Random Number Generators (PRNG), highlighting their differences and uses in cryptography. It further delves into two common RNG algorithms—Linear Congruential Generator (LCG) and Blum Blum Shub (BBS)—with practical examples and exercises. Additionally, stream cipher encryption/decryption using XOR operations is discussed, providing viewers with a comprehensive understanding of how these techniques secure data. The video also includes assignments to help students apply the concepts learned.

Takeaways

• 😀 True Random Number Generators (TRNG) generate random numbers from physical phenomena like mouse movement, keyboard input, and system time, making them ideal for cryptographic use.
• 😀 Pseudo-Random Number Generators (PRNG) generate numbers deterministically from algorithms and are commonly used for cryptographic functions but are not truly random.
• 😀 Linear Congruential Generator (LCG) is a popular PRNG that uses a recurrence relation to generate numbers based on a seed value and a set of constants.
• 😀 The LCG formula is: x_{n+1} = (a * x_n + c) % m, where a, c, and m are constants, and x_n is the seed or previous value.
• 😀 In the example with a = 7, c = 0, and m = 32, the LCG generated a sequence of numbers with a period of 4, demonstrating that LCGs can have repeating cycles.
• 😀 The Blum Blum Shub (BBS) generator is another PRNG that uses two large prime numbers, p and q, to generate secure random numbers for cryptographic purposes.
• 😀 BBS operates using the formula: x_{n+1} = x_n^2 % n, where n = p * q. This method is known for its cryptographic security and unpredictability.
• 😀 Stream ciphers encrypt data bit by bit using a key stream, generated by a PRNG, and are known for their efficiency and speed in encryption.
• 😀 The XOR (exclusive OR) operation is used in stream ciphers to encrypt and decrypt data. When the plaintext and key stream bits differ, the result is 1; when they are the same, the result is 0.
• 😀 In stream cipher encryption, the plaintext is XORed with the key stream to generate ciphertext, and decryption is performed by XORing the ciphertext with the same key stream to recover the original plaintext.

Q & A

What is the difference between a True Random Number Generator (TRNG) and a Pseudo-Random Number Generator (PRNG)?

A True Random Number Generator (TRNG) generates random numbers based on physical phenomena such as atmospheric noise or hardware input. In contrast, a Pseudo-Random Number Generator (PRNG) uses deterministic algorithms to generate a sequence of numbers that appear random, but they are completely determined by an initial 'seed' value.

Why is randomness important in cryptography?

Randomness is crucial in cryptography because it ensures that encryption keys and other security parameters are unpredictable, making it difficult for attackers to break the encryption. Random numbers are used in key generation, initialization vectors, and the creation of secure cryptographic algorithms.

How does the Linear Congruential Generator (LCG) work?

The Linear Congruential Generator (LCG) produces a sequence of pseudo-random numbers using the formula `X(n+1) = (a * X(n) + c) % m`. This equation involves a multiplier `a`, an increment `c`, and a modulus `m`, and starts with an initial value `X0`. The sequence of values generated by the LCG is periodic, meaning it repeats after a certain number of steps.

What is the key limitation of the LCG, as discussed in the script?

The key limitation of the LCG, as explained in the script, is that it can produce a sequence with a short period, meaning it quickly repeats itself. For example, with certain parameters, the LCG can produce only a small set of unique values, making it unsuitable for cryptographic purposes where a larger variety of random values is needed.

What is the Blum Blum Shub Generator, and why is it considered secure?

The Blum Blum Shub (BBS) Generator is a cryptographic random number generator based on the difficulty of factoring large numbers. It uses two large prime numbers `p` and `q` that satisfy `p % 4 = 3` and `q % 4 = 3`, and produces random numbers by squaring a seed value and taking the modulus of `n = p * q`. Its security derives from the fact that breaking its randomness requires factoring large primes, a problem that is computationally hard.

In the script, how are pseudo-random numbers generated using the LCG example `a=7`, `c=0`, `m=32`, and `X0=1`?

For the LCG example with `a=7`, `c=0`, `m=32`, and `X0=1`, the random sequence is generated iteratively using the formula `X(n+1) = (a * X(n) + c) % m`. Starting with `X0 = 1`, the next values are calculated as follows: `X1 = 7`, `X2 = 17`, `X3 = 23`, and the sequence repeats with `X4 = 1`, indicating a short period of only four unique values.

What is the concept of a 'period' in a random number sequence, and how is it relevant to cryptography?

The 'period' of a random number sequence refers to the number of steps it takes before the sequence repeats itself. A short period is undesirable in cryptography because it means that the sequence of random numbers is predictable and can be exploited by attackers. A longer period provides more security by ensuring the randomness persists over a greater number of steps.

How does XOR (exclusive OR) work in stream ciphers for encryption and decryption?

In stream ciphers, XOR (exclusive OR) is used to encrypt and decrypt data bit by bit. The plaintext is XORed with a keystream to produce the ciphertext, and to decrypt, the ciphertext is XORed again with the same keystream. The XOR operation outputs `1` when the bits are different (0 XOR 1 = 1) and `0` when the bits are the same (0 XOR 0 = 0). This symmetry ensures that decryption can reverse the encryption process.

What role do the parameters `p`, `q`, and `n` play in the Blum Blum Shub generator?

In the Blum Blum Shub generator, `p` and `q` are large prime numbers that must satisfy the condition `p % 4 = 3` and `q % 4 = 3`. These primes are multiplied together to form `n`, which is used as the modulus for the random number generation process. The security of the generator relies on the difficulty of factoring `n` into its prime components.

What is the significance of the 'seed' in both LCG and Blum Blum Shub generators?

The 'seed' in both the LCG and Blum Blum Shub generators is the starting value used to initiate the random number sequence. In the LCG, the seed is the initial value `X0`, and in the Blum Blum Shub generator, the seed is the value `S`. The seed plays a critical role in determining the sequence of random numbers generated, and different seeds will produce different sequences.