Data Encryption Standard on Ruby

readme.md

DES

Data Encryption Standard

Kaisetsu

つくってまなぶ★DES☆

Usage

# create operator
operator = DES.new

# set key (8 byte)
operator.key = 'kkeeeyyy'

# set message (8 byte, want to encrypt)
operator.message = 'helllooo'

# encrypt
encmsg = operator.encrypt
#=> some encrypted message

# set message (want to decrypt)
operator.message = encmsg

# decrypt
operator.decrypt
#=> helllooo

# if set wrongkey, you'll get wrong decrypted message
operator.key = 'wrongkey'
operator.decrypt

# on DES, last bit of each bytes on key is used as parity bit
# therefore attacker CAN DECRYPT message without valid key (only need 56bit)
# 'k' = '01101011' 'e' = '01100101' 'y' = '01111001'
# 'j' = '01101010' 'd' = '01100100' 'x' = '01111000'
operator.key = 'jjdddxxx'
operator.decrypt
#=> helllooo

Ref

• http://page.math.tu-berlin.de/~kant/teaching/hess/krypto-ws2006/des.htm
• http://co-akuma.directorz.jp/blog/2012/05/des%E3%81%A8%E3%81%AF%EF%BC%9F/
• https://techracho.bpsinc.jp/baba/2011_08_23/4403
• https://qiita.com/repeatedly/items/727b08599d87af7fa671
• https://carefree-se.hatenablog.com/entry/2016/04/13/235644

des.rb

# frozen_string_literal: true

require 'bundler/inline'

gemfile do
  gem 'test-unit'
  gem 'function_chain'
end

require 'function_chain'
require_relative 'des/constants'
require_relative 'des/exception'

class DES
  include FunctionChain
  attr_reader :key, :key_bin, :message, :message_bin, :keys

  # @param [String] key         encryption/decryption key
  # @param [String] key_bin     binary(0-1 string) key
  # @param [String] message     encrypted/decrypted message text
  # @param [String] message_bin binary(0-1 string) message text
  # @param [Array]  keys        array of sub key which will generate
  #                             IMPORTANT: keys[0] is K1 (be careful of index)
  # @param [Bool]   key_reverse indicate current mode -> (true/false : decrypt/encrypt)
  def initialize
    @key = nil
    @key_bin = nil
    @message = nil
    @message_bin = nil
    @keys = []
    @key_reverse = false
  end

  def inspect
    <<~OUT
      ----- Instance variables -----
      key               : #{key}
      binarized key     : #{key_bin}
      message           : #{message}
      binarized message : #{message_bin}
    OUT
  end

  # @param [String] key encryption/decryption key which is 8 byte
  def key=(key)
    raise InvalidKeyError if key.bytes.size != 8

    @keys.clear
    @key_reverse = false # if new key was set, switch mode to encrypt (DEFAULT) and clear subkeys
    @key = key
  end

  # @param [String] message encryption/decryption message which is 8 byte
  def message=(message)
    raise InvalidMessageError if message.bytes.size != 8

    @message = message
  end

  # encrypt → decrypt → encrypt(keys are defined but reversed, so reverse again and switch mode )
  #                   ^ if change key here, we need to switch mode before generating key
  def encrypt
    reverse_key if decrypt_mode?
    generate_keys
    encode
  end

  def decrypt
    generate_keys
    reverse_key unless decrypt_mode?
    encode
  end

  def generate_keys
    return unless keys.empty?

    c = []
    d = []

    binarize_key!
    permutated_key = permutate_with_pc1
    c << permutated_key[0...28]
    d << permutated_key[28..-1]

    SHIFT.each do |s|
      c << (c.last[s..-1] + c.last[0...s])
      d << (d.last[s..-1] + d.last[0...s])
      @keys << permutate_with_pc2(c.last + d.last)
    end
  end

  def encode
    binarize_message!

    permutated_message = permutate_with_ip
    l_set, r_set = separate_to_lr(permutated_message)
    16.times do |i|
      r = r_set.last
      r_set << operate(i, l_set.last, r)
      l_set << r
    end
    permutate_with_ipinv(r_set.last + l_set.last)
      .yield_self { |binstr| characterize(binstr) }
  end

  def operate(key_index, l_last, r_target)
    RelayChain
      .new(self)
      .add(:permutate_with_e)
      .add { |chain, *working| chain.call(working, key_index) }
      .add(:xor_with_key)
      .add { |chain, *working| chain.call(working) }
      .add(:transpose_with_s_table)
      .add { |chain, *working| chain.call(working) }
      .add(:permutate_with_p)
      .add { |chain, *working| chain.call(working, l_last) }
      .add(:xor_with_l)
      .call(r_target)
  end

  def reverse_key
    @key_reverse = !@key_reverse
    @keys = keys.reverse
  end

  def decrypt_mode?
    @key_reverse
  end

  def binarize_key!
    @key_bin = key.bytes.map { |k| k.to_s(2).rjust(8, '0') }.join
  end

  def binarize_message!
    @message_bin = message.bytes.map { |m| m.to_s(2).rjust(8, '0') }.join
  end

  def permutate_with_pc1
    PC1.map { |index| key_bin.chars[index] }
  end

  # @param [Array] cndn is joined array which is Cn + Dn
  def permutate_with_pc2(cndn)
    PC2.map { |index| cndn[index] }
  end

  def permutate_with_ip
    IP.map { |index| message_bin.chars[index] }
  end

  # @param [Array<String>] permutated_message is set of '0', '1' which is applied IP
  def separate_to_lr(permutated_message)
    [[permutated_message[0...32]], [permutated_message[32..-1]]]
  end

  # @param [Array<String>] r is *R*ight string set of '0', '1'
  def permutate_with_e(r)
    E.map { |index| r[index] }
  end

  # @param [Array<String>] permutated_r is set of '0', '1' which is applied E
  # @param [Integer]       key_index    is index of subkey, key_index = 0 then indicates K1
  def xor_with_key(permutated_r, key_index)
    r_xor_key = []
    permutated_r
      .zip(keys[key_index])
      .each { |right, key| r_xor_key << (right.to_i ^ key.to_i).to_s }
    r_xor_key
  end

  # @param [Array<String>] xored_r is set of '0', '1' which is E(R) XOR K
  def transpose_with_s_table(xored_r)
    transposed_r = []
    xored_r.each_slice(6).with_index do |bits, i|
      x = bits[1..4].join.to_i(2)
      y = (bits[0] + bits[-1]).to_i(2)
      transposed_r += DES::S[i][y][x].to_s(2).rjust(4, '0').split('')
    end
    transposed_r
  end

  # @param [Array<String>] transposed_r is set of '0', '1' which is applied S-table
  def permutate_with_p(transposed_r)
    P.map { |index| transposed_r[index] }
  end

  # @param [Array<String>] permutated_r is set of '0', '1' which is applied P
  # @param [Array<String>] l            is set of '0', '1' last element of L's set
  def xor_with_l(permutated_r, l)
    xored_r = []
    permutated_r
      .zip(l)
      .each { |arr| xored_r << (arr[0].to_i ^ arr[1].to_i).to_s }
    xored_r
  end

  # @param [Array<String>] r16l16 is set of '0', '1' which is created by R16 + L16
  def permutate_with_ipinv(r16l16)
    IPINV.map { |index| r16l16[index] }.join
  end

  # @param [String] binstr is string which contains '0', '1' and length is 64
  def characterize(binstr)
    binstr.scan(/.{8}/).map { |b| b.to_i(2) }.pack('C*')
  end
end

des_constants.rb

# frozen_string_literal: true

class String
  def indexize
    to_i - 1
  end
end

class DES
  PC1 = %w[
    57 49 41 33 25 17 9 1 58 50 42 34 26 18
    10 2 59 51 43 35 27 19 11 3 60 52 44 36
    63 55 47 39 31 23 15 7 62 54 46 38 30 22
    14 6 61 53 45 37 29 21 13 5 28 20 12 4
  ].map(&:indexize).freeze

  PC2 = %w[
    14 17 11 24 1 5 3 28 15 6 21 10
    23 19 12 4 26 8 16 7 27 20 13 2
    41 52 31 37 47 55 30 40 51 45 33 48
    44 49 39 56 34 53 46 42 50 36 29 32
  ].map(&:indexize).freeze

  SHIFT = %w[
    1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
  ].map(&:to_i).freeze

  IP = %w[
    58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
    62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
    57 49 41 33 25 17 09 1 59 51 43 35 27 19 11 3
    61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7
  ].map(&:indexize).freeze

  P = %w[
    16 7 20 21 29 12 28 17
    1 15 23 26 5 18 31 10
    2 8 24 14 32 27 3 9
    19 13 30 6 22 11 4 25
  ].map(&:indexize).freeze

  IPINV = %w[
    40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
    38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
    36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
    34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25
  ].map(&:indexize).freeze

  E = %w[
    32 1 2 3 4 5 4 5 6 7 8 9
    8 9 10 11 12 13 12 13 14 15 16 17
    16 17 18 19 20 21 20 21 22 23 24 25
    24 25 26 27 28 29 28 29 30 31 32 1
  ].map(&:indexize).freeze

  S = [
    [
      %w[14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7].map(&:to_i),
      %w[0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8].map(&:to_i),
      %w[4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0].map(&:to_i),
      %w[15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13].map(&:to_i)
    ],
    [
      %w[15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10].map(&:to_i),
      %w[3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5].map(&:to_i),
      %w[0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15].map(&:to_i),
      %w[13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9].map(&:to_i)
    ],
    [
      %w[10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8].map(&:to_i),
      %w[13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1].map(&:to_i),
      %w[13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7].map(&:to_i),
      %w[1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12].map(&:to_i)
    ],
    [
      %w[7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15].map(&:to_i),
      %w[13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9].map(&:to_i),
      %w[10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4].map(&:to_i),
      %w[3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14].map(&:to_i)
    ],
    [
      %w[2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9].map(&:to_i),
      %w[14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6].map(&:to_i),
      %w[4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14].map(&:to_i),
      %w[11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3].map(&:to_i)
    ],
    [
      %w[12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11].map(&:to_i),
      %w[10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8].map(&:to_i),
      %w[9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6].map(&:to_i),
      %w[4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13].map(&:to_i)
    ],
    [
      %w[4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1].map(&:to_i),
      %w[13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6].map(&:to_i),
      %w[1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2].map(&:to_i),
      %w[6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12].map(&:to_i)
    ],
    [
      %w[13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7].map(&:to_i),
      %w[1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2].map(&:to_i),
      %w[7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8].map(&:to_i),
      %w[2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11].map(&:to_i)
    ]
  ].freeze
end

des_exception.rb

# frozen_string_literal: true

class DES
  class InvalidKeyError < StandardError
    def initialize
      super('Encryption/Decryption key must be 8 characters')
    end
  end

  class InvalidMessageError < StandardError
    def initialize
      super('Message must be 8 characters')
    end
  end
end

des_test.rb

# frozen_string_literal: true

require 'test/unit'
require_relative 'des'

class DESTest < Test::Unit::TestCase
  class << self
    def startup
      key_hex = '133457799BBCDFF1'
      @@key =
        key_hex
        .chars
        .map { |c| c.to_i(16) }
        .map { |b| b.to_s(2).rjust(4, '0') }
        .each_slice(2).to_a
        .map { |b2| b2.join.to_i(2) }
        .pack('C*')

      msg_hex = '0123456789ABCDEF'
      @@message =
        msg_hex
        .chars
        .map { |c| c.to_i(16) }
        .map { |b| b.to_s(2).rjust(4, '0') }
        .each_slice(2).to_a
        .map { |b2| b2.join.to_i(2) }
        .pack('C*')

      @@keys_for_assert = %w[
        000110110000001011101111111111000111000001110010
        011110011010111011011001110110111100100111100101
        010101011111110010001010010000101100111110011001
        011100101010110111010110110110110011010100011101
        011111001110110000000111111010110101001110101000
        011000111010010100111110010100000111101100101111
        111011001000010010110111111101100001100010111100
        111101111000101000111010110000010011101111111011
        111000001101101111101011111011011110011110000001
        101100011111001101000111101110100100011001001111
        001000010101111111010011110111101101001110000110
        011101010111000111110101100101000110011111101001
        100101111100010111010001111110101011101001000001
        010111110100001110110111111100101110011100111010
        101111111001000110001101001111010011111100001010
        110010110011110110001011000011100001011111110101
      ]
    end
  end

  def setup
    @des = DES.new
  end

  test 'All subkeys are valid' do
    @des.key = @@key
    @des.generate_keys
    @des.keys.each_with_index do |gen_key, i|
      assert_equal gen_key.join, @@keys_for_assert[i]
    end
  end

  test 'Applying IP to message will return valid binaries' do
    @des.message = @@message
    @des.binarize_message!

    assert_equal @des.permutate_with_ip.join, '1100110000000000110011001111111111110000101010101111000010101010'
  end

  test 'DES#separate_to_lr will return 1 Array includes 2 Arrays which is separated from IP permutated R' do
    @des.message = @@message
    @des.binarize_message!
    permutated_message = @des.permutate_with_ip
    l_set, r_set = @des.separate_to_lr(permutated_message)

    assert_equal l_set.join, '11001100000000001100110011111111'
    assert_equal r_set.join, '11110000101010101111000010101010'
  end

  test 'Applying E to R0 will return valid binaries' do
    @des.message = @@message
    @des.binarize_message!
    permutated_message = @des.permutate_with_ip
    _, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last

    assert_equal @des.permutate_with_e(r0).join, '011110100001010101010101011110100001010101010101'
  end

  test 'Operate K1 xor E(R0) will return valid binaries' do
    @des.key = @@key
    @des.generate_keys
    @des.message = @@message
    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    _, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last
    permutated_r = @des.permutate_with_e(r0)

    assert_equal @des.xor_with_key(permutated_r, 0).join, '011000010001011110111010100001100110010100100111'
  end

  test 'Operate S table to XORed statement will return valid binaries' do
    @des.key = @@key
    @des.generate_keys
    @des.message = @@message
    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    _, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last
    permutated_r = @des.permutate_with_e(r0)
    xored_r = @des.xor_with_key(permutated_r, 0)

    assert_equal @des.transpose_with_s_table(xored_r).join, '01011100100000101011010110010111'
  end

  test 'Applying P to S-operated R will return valid binaries' do
    @des.key = @@key
    @des.generate_keys
    @des.message = @@message
    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    _, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last
    permutated_r = @des.permutate_with_e(r0)
    xored_r = @des.xor_with_key(permutated_r, 0)
    transposed_r = @des.transpose_with_s_table(xored_r)

    assert_equal @des.permutate_with_p(transposed_r).join, '00100011010010101010100110111011'
  end

  test 'Assert L0 XOR F(R0, K1) is valid' do
    @des.key = @@key
    @des.generate_keys
    @des.message = @@message
    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    l_set, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last
    permutated_r = @des.permutate_with_e(r0)
    xored_r = @des.xor_with_key(permutated_r, 0)
    transposed_r = @des.transpose_with_s_table(xored_r)
    permutated_r = @des.permutate_with_p(transposed_r)
    l0 = l_set.last

    assert_equal @des.xor_with_l(permutated_r, l0).join, '11101111010010100110010101000100'
  end

  test 'Assert function chain will be working correctly' do
    @des.key = @@key
    @des.generate_keys
    @des.message = @@message
    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    l_set, r_set = @des.separate_to_lr(permutated_message)
    r0 = r_set.last

    result = @des.xor_with_l(
      @des.permutate_with_p(
        @des.transpose_with_s_table(
          @des.xor_with_key(
            @des.permutate_with_e(r0), 0))), l_set.last)

    assert_equal result.join, '11101111010010100110010101000100'
  end

  test 'Assert R16 L16 is valid binaries' do
    @des.key = @@key
    @des.message = @@message
    @des.generate_keys

    @des.binarize_message!

    permutated_message = @des.permutate_with_ip
    l_set, r_set = @des.separate_to_lr(permutated_message)
    16.times do |i|
      r = r_set.last
      result = @des.xor_with_l(
        @des.permutate_with_p(
          @des.transpose_with_s_table(
            @des.xor_with_key(
              @des.permutate_with_e(r), i))), l_set.last)
      l_set << r
      r_set << result
    end

    assert_equal l_set.last.join, '01000011010000100011001000110100'
    assert_equal r_set.last.join, '00001010010011001101100110010101'
  end

  test 'Assert encryption complate' do
    @des.key = @@key
    @des.message = @@message
    encrypted = @des.encrypt
    encrypted_bin = encrypted.bytes.map { |b| b.to_s(2).rjust(8, '0') }.join

    assert_equal encrypted_bin, '1000010111101000000100110101010000001111000010101011010000000101'
  end

  test 'Assert decryption complate' do
    @des.key = @@key
    @des.message = @@message

    enc_message = @des.encrypt
    @des.message = enc_message

    assert_equal @des.decrypt, @@message
  end
end