Winter School is Coming

Winter School is a course in cryptography. The course features weekly assignments and review sessions on Mondays.

You can join the Winter School at WellingtonRuby. If you have any questions just comment on the Winter School events there.

Shuffle Puzzle

Winter School will start in June. Try the Shuffle Puzzle while you wait!

java.util.Random generates pseudorandom numbers from a linear congruential generator.

You can implement that generator in Ruby like this:

## <>
##   @state: Integer
class Generator
	A = 0x000000000000000B
	F = 0x00000005DEECE66D
	M = 0x0000FFFFFFFFFFFF

	## Integer -> void
	def initialize(seed)
		super()
		@state = (seed ^ F) & M
		return
	end

	## -> Integer
	def __next
		return @state = (A + F * @state) & M
	end

	## Integer -> Integer
	def random(n)
		unless n > 0
			raise ArgumentError.new("n must be positive")
		end
		if n == n & -n
			k = __next >> 17
			return (n * k) >> 31
		else
			while true
				k = __next >> 17
				r = k % n
				if k - r + n - 1 < 0x80000000
					return r
				end
			end
		end
	end
end

Try the generator:

seed = 0x0000000000000000
g = Generator.new(seed)
8.times do |j|
	puts g.random(j + 1)
end
0
1
1
2
0
5
2
0

Now use the generator to implement a shuffle with the Fisher–Yates algorithm:

## <>
module Util
	class << self
		## <E: ..Object?> Generator, Integer, &{Integer -> E} -> Array<E>
		def shuffle(g, n)
			a = Array.new(n)
			j = 0
			while j < n
				k = j + 1
				i = g.random(k)
				if i != j
					a[j] = a[i]
				end
				a[i] = yield(j)
				j = k
			end
			return a
		end
	end
end

Perform a shuffle:

seed = 0x0000000000000000
g = Generator.new(seed)
a = Util.shuffle(g, 8) { |v| v }
puts a
7
2
6
1
0
5
3
4

Implement a class for cards:

## <>
##   @v: Integer
class Card
	RANKS = "A23456789TJQK".chars
	SUITS = "♣♦♥♠".chars

	## Integer -> void
	def initialize(v)
		super()
		@v = v
		return
	end

	## -> String
	def to_s
		return RANKS.fetch(@v >> 2) + SUITS.fetch(@v & 3)
	end
end

Create some cards:

13.times do |r|
	v = r << 2 | 3
	c = Card.new(v)
	puts c
end
A♠
2♠
3♠
4♠
5♠
6♠
7♠
8♠
9♠
T♠
J♠
Q♠
K♠

Implement a class for decks:

## <>
##   @a: Array<Card>
class Deck
	N = Card::RANKS.size * Card::SUITS.size

	## Generator -> void
	def initialize(g)
		super()
		@a = Util.shuffle(g, N) { |v| Card.new(v) }
		return
	end

	## -> String
	def to_s
		return @a.join(" ")
	end
end

Create a deck:

seed = 0x0000000000000000
g = Generator.new(seed)
d1 = Deck.new(g)
puts d1
5♠ T♣ J♠ 5♣ 3♦ 9♦ 7♦ 6♥ J♥ A♣ 2♥ 6♠ K♦ ...

Create another deck using the same generator:

# ...

d2 = Deck.new(g)
puts d2
5♦ 5♣ 2♥ Q♠ 7♥ T♣ 3♠ J♠ 3♦ 9♥ 3♣ Q♥ 6♠ ...

Now break java.util.Random!

Can you determine the second deck given the first deck?

You can do it in three steps:

  1. determine the outputs of the generator for the first deck (easy)
  2. determine the state of the generator for the first deck (hard)
  3. determine the outputs of the generator for the second deck (easy)

That’s all folks

Follow @InfraRuby on Twitter
Copyright © 2011-2017 InfraRuby Vision Limited