From 1fd84c7dc70a0a6e6d8651fafa50c51dd697ae77 Mon Sep 17 00:00:00 2001 From: Benedict Date: Thu, 2 Feb 2017 00:32:26 +0100 Subject: added random stuff which hasn't beend added because yeah --- lib/mt_19937_tempering.txt | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 lib/mt_19937_tempering.txt (limited to 'lib/mt_19937_tempering.txt') diff --git a/lib/mt_19937_tempering.txt b/lib/mt_19937_tempering.txt new file mode 100644 index 0000000..dfdda7a --- /dev/null +++ b/lib/mt_19937_tempering.txt @@ -0,0 +1,34 @@ +Why can we reverse the tempering function? + +There are to kinds of operations in the tempering function of the MT: + + 1) Right shift + 2) Left shift with an AND + +To undo the first operation, a simple shift is straight forward. Let's consider +the following example of a 24-bit number + + 0010 1010 1011 1101 1111 0111 y + 0000 0000 0000 0000 0000 1010 1010 1111 0111 1101 11 y >> 18 := N + ^ + orginal string + 0010 1010 1011 1101 1111 1101 y ^ (y>>18) := M + + +On can see, that the first 18 bits of M are the same than y. That's clear, +because we have shifted 18 new 0 into it. But now we also now N completly, since +the last 6 bits are the first 6 of M (N is a shifted version of M). +If you shift less than 24/2 = 12 bits, you have to do the above steps in a +loop, because you cannot determin N completly one step. + +To understand why one can undo the second operation was a bit harder for me. +For me it was the easiest to understand it with the feistel network. + + + y y << 15 + | | + | | + XOR<--------- F <----------- + | | + \_______________________ / + /\______________________ -- cgit v1.2.3-70-g09d2