Private-Key Encryption - Introduction to Cryptography with Maple - page 162

happens when automatic seeding is used and then we show how an attacker can easily
break the scheme implemented in POTP even if a key of more than 300 bits is used
(assuming that this key was obtained by using Mersenne Twister with automatic
seeding).
Let us start by calling randomize() to initialize Mersenne Twister and then
using RandomTools:-MersenneTwister:-GenerateInteger to gener-
ate a large integer to be used as a seed for BBS:
> s := randomize();
RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 10ˆ99 .. 10ˆ100);
4680868547622918676426318327358271319529290338078826461883520057763260168891192866\
909615753148750450
Now, s holds the value of the seed used for Mersenne Twister and we can recover
the large integer value generated by just calling:
> RandomTools:-MersenneTwister:-SetState(state = s);
RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 10ˆ99 .. 10ˆ100);
4680868547622918676426318327358271319529290338078826461883520057763260168891192866\
909615753148750450
A similar thing happens if we use the alternative method to automatically seed
Mersenne Twister:
> kernelopts(opaquemodules = false):
s := RandomTools:-MersenneTwister:-MTKernelInterface(1):
RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 10ˆ99 .. 10ˆ100);
5079619402809231831169214173347279132375830016394640834053224365559846124843647276\
134468592152981428
> RandomTools:-MersenneTwister:-SetState(state = s):
RandomTools:-MersenneTwister:-GenerateInteger(':-range' = 10ˆ99 .. 10ˆ100);
5079619402809231831169214173347279132375830016394640834053224365559846124843647276\
134468592152981428
What happens then if we use an integer of 100 decimal digits, obtained as above,
as the POTP key? The answer is that, although this key has more than 300 bits, the
security it provides is no higher than that offered by a 32-bit random key and this
would also be the case even if a cryptographically secure PRG were used to generate
the key from the automatic seed. Roughly speaking, this is due to the fact that the
PRG is a deterministic algorithm that does not increase the randomness already
present in its seed: it merely stretches the seed. In other words, the reason is that the
key thus produced is not random (i.e., these keys are not chosen according to the
uniform distribution among strings of their size) and, since we used a 31-bit seed
for Mersenne Twister, the number of possible keys obtained this way is at most 2 31
and so the system would be vulnerable to a brute-force attack. Let's give a specific
example. Suppose that Eve observes the following ciphertext that Alice sent to Bob:
> c := "ffa93d77b3407b58b55b3d91065456ef1f59695f7ad7ade78dceaa4f0ade52242b75566379\
bc2d8cdd2cadf0ca194bef":
Eve knows the plaintext was encrypted with POTP and suspects that Alice and
Bob chose their secret key by usingMaple's randomize() to obtain a seed and then