class CryptoToolchain::Utilities::MT19937
Constants
- PARAMETERS_32
- PARAMETERS_64
Attributes
index[RW]
seed[RW]
state[RW]
Public Class Methods
from_array(arr, bits: 32, index: parameters_for(bits).fetch(:n))
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 26 def self.from_array(arr, bits: 32, index: parameters_for(bits).fetch(:n)) mt = new(0, bits: bits) mt.send(:state=, arr) mt.send(:index=, index) mt end
new(seed, bits: 32)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 44 def initialize(seed, bits: 32) @seed = seed set_vars!(self.class.parameters_for(bits)) @index = n @state = build_state! end
parameters_for(bits)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 33 def self.parameters_for(bits) case bits when 32 PARAMETERS_32 when 64 PARAMETERS_64 else raise ArgumentError.new("Bits must be 32 or 64") end end
Public Instance Methods
==(other)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 51 def ==(other) return false unless other.is_a?(self.class) other.send(:state) == state && other.send(:index) == index end
extract()
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 56 def extract twist! if index >= n temper(state[index]) ensure @index += 1 end
temper(y)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 63 def temper(y) y ^= (y >> u) & d y ^= (y << s) & b y ^= (y << t) & c y ^= (y >> l) lowest_bits(y) end
untemper(y)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 71 def untemper(y) y = untemper_rshift(y, shift: l) y = untemper_lshift(y, shift: t, mask: c) y = untemper_lshift(y, shift: s, mask: b) untemper_rshift(y, shift: u, mask: d) end
Private Instance Methods
build_state!()
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 175 def build_state! _state = [seed] for i in (1...n) prev = _state[i - 1] val = lowest_bits((f * (prev ^ (prev >> (w-2)) ) + i)) _state << val end _state end
defunct_untemper_step_for_posterity(y, debug: false)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 111 def defunct_untemper_step_for_posterity(y, debug: false) # We're reversing # y ^= (y << 7) & 0x9d2cf80 # so, take the bottom 25 bits of y, shift them over, and & that with the constant 0x9d2c5680, # and xor the result with the top 25 bits of y. Notably, this leaves the bottom 7 bits of y # untouched. The general idea is that we iteratively recover bits. The input shares the bottom 7 # bits with the proper output. We work in 7-bit chunks (the last chunk is only 4 bits of course), # shifting and xor-ing (and &ing with the appropriate chunk of the mask) as we go. # # This algorithm never has varying periodicity, unlike the brute force method above. My current # thought is that this is because I'm not appropriately breaking the mask up into chunks like I do # here, but I'm not quite sure. For now, I'll stick with the naive algorithm until I have a complete # understanding of this one. if debug puts " y #{y.to_bits} #{y}" puts puts "y<<7 #{((y<<7) & 0xffffffff).to_bits}" puts "&with #{(0x00003f80 & b).to_bits}" puts " = #{((y << 7) & (0x00003f80 & b)).to_bits}" puts "xor y #{y.to_bits}" end y ^= (y << 7) & (0x00003f80 & b) if debug puts " = #{y.to_bits}" puts puts "y<<7 #{((y<<7) & 0xffffffff).to_bits}" puts "&with #{(0x001fc000 & b).to_bits}" puts " = #{((y << 7) & (0x001fc000 & b)).to_bits}" puts "xor y #{y.to_bits}" end y ^= (y << 7) & (0x001fc000 & b) if debug puts " = #{y.to_bits}" puts puts "y<<7 #{((y<<7) & 0xffffffff).to_bits}" puts "&with #{(0x0fe00000 & b).to_bits}" puts " = #{((y << 7) & (0x0fe00000 & b)).to_bits}" puts "xor y #{y.to_bits}" end y ^= (y << 7) & (0x0fe00000 & b) if debug puts " = #{y.to_bits}" puts puts "y<<7 #{((y<<7) & 0xffffffff).to_bits}" puts "&with #{(0xf0000000 & b).to_bits}" puts " = #{((y << 7) & (0xf0000000 & b)).to_bits}" puts "xor y #{y.to_bits}" end y ^= (y << 7) & (0xf0000000 & b) if debug puts " = #{y.to_bits}" puts y end y end
lower_mask()
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 199 def lower_mask @lower_mask ||= (1 << r) - 1 end
lowest_bits(num)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 213 def lowest_bits(num) num & 0xffffffff end
set_vars!(parameters)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 207 def set_vars!(parameters) parameters.each do |k, v| instance_variable_set("@#{k}", v) end end
twist!()
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 185 def twist! for i in (0...n) cur = state[i] x = (cur & upper_mask) + (state[(i+1) % n] & lower_mask) xA = x >> 1 if (x % 2) != 0 xA = xA ^ a end state[i] = state[(i + m) % n] ^ xA end @index = 0 nil end
untemper_lshift(val, shift: , mask: 0xffffffff)
click to toggle source
General principle:
x ^= (x << y) is periodic.
What we want to do, then, is exploit this periodicity:
a -> b -> c -> d ^ v |------<-------|
Where the temper function went from c -> d, we want to go d->a->b->c to untemper So we do the most naive thing possible, rather than the performant method below which never quite clicked in the ol' brain
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 93 def untemper_lshift(val, shift: , mask: 0xffffffff) original = val loop do prev = val val ^= ((val << shift) & mask) return prev if val == original end end
untemper_rshift(val, shift: , mask: 0xffffffff)
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 102 def untemper_rshift(val, shift: , mask: 0xffffffff) original = val loop do prev = val val ^= ((val >> shift) & mask) return prev if val == original end end
upper_mask()
click to toggle source
# File lib/crypto_toolchain/utilities/mt_19937.rb, line 203 def upper_mask @upper_mask ||= lowest_bits(~lower_mask) end