ElGamal暗号とRSA暗号とRSA署名

(僕と同じ大学の|これらを実装しなければならない)人、どうぞ。遅くて実用性はありませんが、ご自由にお使いください。

ライブラリ配置

  |-+ $RUBYLIBが通ってるディレクトリ
    |-- publickeycryptosystem.rb
    |-+ publickeycryptosystem
      |--elgamal.rb
      |--rsa.rb
      |--utils.rb  

ライブラリソース

publickeycryptosystem.rb

module PublicKeyCryptosystem
  VERSION = "0.0.1"
  DEBUG = false
end

elgamal.rb

# ElGamal Encrypton for Ruby
# 

require 'publickeycryptosystem'
require 'publickeycryptosystem/utils'

module PublicKeyCryptosystem

  module ElGamal

    extend Utils


    class PublicKey

      include Utils

      def initialize(bit_length, p, g, y)
        @split_length = bit_length - 1
        @p = p
        @g = g
        @y = y
      end
      attr_reader :split_length, :p, :g, :y
      
      def encode(message)
        r = rand(@p - 1) + 1
        c1 = expmod(@g, r, @p)
        unpacked = message.unpack("b*")[0].scan(/.{1,#{@split_length.to_s}}/)
        y1 = expmod(@y, r, @p)
        c2s = unpacked.collect do |bits|
          expmod(Integer("0b#{bits}") * y1, 1, @p)
        end        
        Cryptogram.new(c1, c2s, @split_length - unpacked[-1].length)
      end
    end
    

    class PrivateKey

      include Utils

      def initialize(bit_length, p, x)
        @split_length = bit_length - 1
        @p = p
        @x = x
      end
      attr_reader :split_length, :p, :x
      
      def decode(crypt)
        c3 = expmod(crypt.c1, @p - 1 - @x, @p)
        unpacked = crypt.c2s.collect do |c2|
          bits = sprintf("%#b", (c2 * c3).modulo(@p))[2..-1]
          "0" * (@split_length - bits.length) + bits
        end
        unpacked[-1] = unpacked[-1][crypt.padding..-1]
        [unpacked.join("")].pack("b*")
      end
    end
    

    class Cryptogram
      def initialize(c1, c2s, padding)
        @c1 = c1
        @c2s = c2s
        @padding = padding
      end
      attr_reader :c1, :c2s, :padding
      def decode(private_key)
        private_key.decode(this)
      end
    end
    

    def make_key(bit_length)
      pair = generate_prime_and_primitive_root(bit_length)
      p = pair[:prime]
      g = pair[:primitive_root]
      x = rand(p - 1) + 1
      y = expmod(g, x, p)
      return {:public  => PublicKey.new(bit_length, p,g,y),
              :private => PrivateKey.new(bit_length, p,x)   }
    end
    module_function :make_key
  end
end

rsa.rb

# RSA Encrypton for Ruby
# 

require 'digest/sha2'
class Digest::Base
  def self.open(path)
    obj = new
    File.open(path, 'rb') {|f|
      buf = ""
      while f.read(256, buf)
        obj << buf
      end
    }
    obj
  end
  def self.read(io)
    obj = new
    buf = ""
    while io.read(256, buf)
      obj << buf
    end
    obj
  end
end


require 'publickeycryptosystem/utils'
require 'publickeycryptosystem'

module PublicKeyCryptosystem
  
  module RSA
    
    extend Utils
    
    
    class PublicKey
      
      include Utils
      
      def initialize(bit_length, n, e)
        @split_length = bit_length - 1
        @n = n
        @e = e
      end
      attr_reader :split_length, :n, :e
      
      def encode(message)
        unpacked = message.unpack("b*")[0].scan(/.{1,#{@split_length.to_s}}/)
        padding = @split_length - unpacked[-1].length
        cs = unpacked.collect do |bits|
          expmod(Integer("0b#{bits}") , @e, @n)
        end        
        Cryptogram.new(cs, padding)
      end
      
      def verify?(sign, str_or_io)
        if str_or_io.kind_of? String
          h = Integer("0x#{Digest::SHA256.hexdigest(str_or_io)}")
        else
          h = Integer("0x#{Digest::SHA256.read(str_or_io).hexdigest}")
        end
        expmod(sign.sign, @e, @n) == h % @n
      end

      def verify_file?(sign, file)
        h = Integer("0x#{Digest::SHA256.open(path).hexdigest}")        
        expmod(sign.sign, @e, @n) == h % @n
      end
    end
    
    
    class PrivateKey
      
      include Utils
      
      def initialize(bit_length, n, d)
        @split_length = bit_length - 1
        @n = n
        @d = d
      end
      attr_reader :split_length, :n, :d
      
      def decode(crypt)
        unpacked = crypt.cs.collect do |c|
          bits = sprintf("%#b", expmod(c, @d, @n))[2..-1]
          "0" * (@split_length - bits.length) + bits
        end
        unpacked[-1] = unpacked[-1][crypt.padding..-1]
        [unpacked.join("")].pack("b*")
      end
      
      def signature(str_or_io)
        if str_or_io.kind_of? String
          h = Integer("0x#{Digest::SHA256.hexdigest(str_or_io)}")
        else
          h = Integer("0x#{Digest::SHA256.read(str_or_io).hexdigest}")
        end
        Signature.new(expmod(h, @d, @n))
      end
      def signature_file(path)
        h = Integer("0x#{Digest::SHA256.open(path).hexdigest}")
        Signature.new(expmod(h, @d, @n))
      end
    end
    
    
    class Cryptogram
      def initialize(cs, padding)
        @cs = cs
        @padding = padding
      end
      attr_reader :cs, :padding
      def decode(private_key)
        private_key.decode(this)
      end
    end
    
    class Signature
      def initialize(sign)
        @sign = sign
      end
      attr_reader :sign
      def verify?(public_key, str_or_io)
        public_key.verify? self, str_or_io
      end
      def verify_file?(public_key, file)
        public_key.verify_file? self, file
      end
    end
    
    
    def make_key(bit_length)
      if bit_length % 2 == 0
        p_length = q_length = bit_length / 2
      else
        p_length = bit_length / 2
        q_length = bit_length / 2 + 1
      end
      n, e, d = loop do 
        p = generate_prime(p_length)
        q = generate_prime(q_length)
        next if p == q # same is error

        n = p * q
        next if n >> (bit_length - 1) == 0 # n's bit length != bit_length
        
        # search e
        p_minus_1_times_q_minus_1 = (p - 1)*(q - 1)
        e = loop do
          e = rand(p_minus_1_times_q_minus_1 - 1) + 1
          break e if p_minus_1_times_q_minus_1.gcd(e) == 1
        end
 
        # search inverse element (=d)
        dummy, dummy, inverse_element =
          extended_euclidean(p_minus_1_times_q_minus_1, e)
        
        if inverse_element > 0
          d = inverse_element
          break n, e, d
        end
      end

      return {:public  => PublicKey.new(bit_length, n, e),
              :private => PrivateKey.new(bit_length, n, d) }
    end
    module_function :make_key
  end
end

utils.rb

# Public-key cryptosystem's utility
# 

require 'rational'

module PublicKeyCryptosystem
  module Utils
    module_function

    def expmod(base, exp, m)
      if exp == 0
        1
      elsif exp & 0b1 == 0 # even
        n = expmod(base, exp.div(2), m)
        (n * n) % m
      else # odd
        (base * expmod(base, exp - 1, m)) % m
      end
    end

    def extended_euclidean(a, b)
      if a < b
        a, b = b, a
      end
      a_i_minus_1, x_i_minus_1, y_i_minus_1 = a, 1, 0
      a_i,         x_i,         y_i         = b, 0, 1
      while (a_i != 0)
        q_i_plus_1 = a_i_minus_1 / a_i
        a_i_plus_1 = a_i_minus_1 - q_i_plus_1 * a_i
        x_i_plus_1 = x_i_minus_1 - q_i_plus_1 * x_i
        y_i_plus_1 = y_i_minus_1 - q_i_plus_1 * y_i

        a_i_minus_1, x_i_minus_1, y_i_minus_1 = a_i,        x_i,        y_i
        a_i,         x_i,         y_i         = a_i_plus_1, x_i_plus_1, y_i_plus_1
      end
      d, x, y = a_i_minus_1, x_i_minus_1, y_i_minus_1
      return d, x, y
    end

    def generate_prime_and_primitive_root(bit_length)
      loop do 
        q = generate_prime(bit_length - 1)
        if prime?((q << 1) + 1) # prime?(2*q + 1)
          p = (q << 1) + 1
          loop do
            g = rand(p - 1) + 1
            if expmod(g, 2, p) != 1 && expmod(g, q, p) != 1
              return {:prime => p, :primitive_root => g} 
            end
          end
        end
      end
    end

    def generate_prime(bit_length)
      loop do
        n = generate_random_bits(bit_length)
        return n if prime? n
      end
    end

    def prime?(n)
      return false if n < 2
      return true  if n == 2
      return false if (n & 0b1) == 0 # even number is composite
      return miller_rabin_test(n, 100) == :prime
    end
    
    def miller_rabin_test(n, t)
      # search s,r (n-1 = 2**s * r, r is odd)
      s = 1
      r = 1
      loop do
        r, m = (n - 1).divmod(1 << s) # 1 << s = 2**s
        break if m == 0 && r % 2 == 1
        s = s + 1
      end
      
      # test
      t.times do |dummy|
        y_0 = expmod((rand(n - 1) + 1), r, n)
        next if y_0 == 1 || y_0 == (n - 1)
        
        result = Array(s - 1).inject(y_0) do |old, dummy|
          new = expmod(old, 2, n)
          break if new == n - 1 
          new
        end
        next unless result
        
        return :composite
      end
    
      return :prime
    end

    private
    def generate_random_bits(bit_length)
      Array.new(bit_length - 1).inject(1) do |result, dummy|
        (result << 1) | rand(2)
      end
    end
  end
end

コマンドソース

elgamalkeygen.rb

#/usr/bin/env ruby
# genetate ElGamal publib private key

require 'optparse'
require 'yaml'

require 'publickeycryptosystem/elgamal'

def main
  bit_length = 10
  public_key_file = nil
  private_key_file = nil

  parser = OptionParser.new
  parser.banner = "Usage: #{File.basename($0)} [options]"
  parser.on('--bits=BITS',Integer,
            'Number of bits in the key to create.') {|bits|
    bit_length = bits
  }
  parser.on('--public=FILENAME', 'public key output') {|name|
    public_key_file = name;
  }
  parser.on('--private=FILENAME', 'private key output') {|name|
    private_key_file = name;
  }
  parser.on('--help', 'Prints this message and quit') {
    puts parser.help
    exit 0;
  }
  begin
    parser.parse!
  rescue OptionParser::ParseError => err
    $stderr.puts err.message
    $stderr.puts parser.help
    exit 1
  end

  begin
    keys = PublicKeyCryptosystem::ElGamal.make_key(bit_length)

    public_output = $stdout
    public_output = File.open(public_key_file, "w") if public_key_file
    public_output.puts YAML.dump(keys[:public])
    public_output.close if public_key_file

    private_output = $stdout
    private_output = File.open(private_key_file, "w") if private_key_file
    private_output.puts YAML.dump(keys[:private])
    private_output.close if private_key_file
  rescue => err
    $stderr.puts err.message
    exit 1
  end
end

main

elgamalencode.rb

#/usr/bin/env ruby
# genetate ElGamal cryptogram

require 'optparse'
require 'yaml'

require 'publickeycryptosystem/elgamal'

def main
  public_key_file = nil
  message_file = nil
  cryptogram_file = nil
  parser = OptionParser.new
  parser.banner = "Usage: #{File.basename($0)} [options] <public key>"
  parser.on('--cryptogram=FILEANME', 'cryptogram output file') {|name|
    cryptogram_file = name
  }
  parser.on('--message=FILENAME', 'message input file') {|name|
    message_file = name;
  }
  parser.on('--help', 'Prints this message and quit') {
    puts parser.help
    exit 0;
  }
  begin
    parser.parse!
  rescue OptionParser::ParseError => err
    $stderr.puts err.message
    $stderr.puts parser.help
    exit 1
  end
  unless ARGV.size == 1
    $stderr.puts "too many argument or no argument"
    $stderr.puts parser.help
    exit 1
  end
  public_key_file = ARGV.shift

  begin
    public_key = YAML.load_file(public_key_file)
    unless public_key.instance_of? PublicKeyCryptosystem::ElGamal::PublicKey
      raise StandardError.new("no public key file")
    end

    message_input = STDIN
    message_input = File.open(message_file, "r") if message_file
    message = message_input.read()
    message_input.close if message_file

    cryptogram = public_key.encode(message)

    cryptogram_output = STDOUT
    cryptogram_output = File.open(cryptogram_file, "w") if cryptogram_file
    cryptogram_output.puts(YAML.dump(cryptogram))
    cryptogram_output.close if cryptogram_file
  rescue => err
    $stderr.puts err.message
    exit 1
  end
end

main

elgamaldecode.rb

#/usr/bin/env ruby
# decode ElGamal cryptogram

require 'optparse'
require 'yaml'

require 'publickeycryptosystem/elgamal'

def main
  private_key_file = nil
  message_file = nil
  cryptogram_file = nil
  parser = OptionParser.new
  parser.banner = "Usage: #{File.basename($0)} [options] <private key>"
  parser.on('--cryptogram=FILENAME', 'cryptogram input file') {|name|
    cryptogram_file = name;
  }
  parser.on('--message=FILENAME', 'message output file') {|name|
    message_file = name;
  }
  parser.on('--help', 'Prints this message and quit') {
    puts parser.help
    exit 0;
  }
  begin
    parser.parse!
  rescue OptionParser::ParseError => err
    $stderr.puts err.message
    $stderr.puts parser.help
    exit 1
  end
  unless ARGV.size == 1
    $stderr.puts "too many argument or no argument"
    $stderr.puts parser.help
    exit 1
  end
  private_key_file = ARGV.shift

  begin
    private_key = YAML.load_file(private_key_file)
    unless private_key.instance_of? PublicKeyCryptosystem::ElGamal::PrivateKey
      raise StandardError.new("no private key file")
    end

    if cryptogram_file
      cryptogram = YAML.load_file(cryptogram_file)
    else
      cryptogram = YAML.load(STDIN)
    end
    unless cryptogram.instance_of? PublicKeyCryptosystem::ElGamal::Cryptogram
      raise StandardError.new("no cryptogram file")
    end

    message = private_key.decode(cryptogram)

    message_output = $stdout
    message_output = File.open(message_file, "w") if message_file
    message_output.puts message
    message_output.close if message_file
  rescue => err
    $stderr.puts err.message
    exit 1
  end
end

main

digitalsignature.rb

#/usr/bin/env
# digital signature test

require 'optparse'
require 'pp'
require 'publickeycryptosystem/rsa'

def main
  bit_length = 10
  message_file = nil

  parser = OptionParser.new
  parser.banner = "Usage: #{File.basename($0)} [options]"
  parser.on('--bits=BITS',Integer,
            'Number of bits in the key to create.') {|bits|
    bit_length = bits
  }
  parser.on('--message=FILENAME', 'message input file') {|name|
    message_file = name;
  }
  parser.on('--help', 'Prints this message and quit') {
    puts parser.help
    exit 0;
  }

  begin
    parser.parse!
  rescue OptionParser::ParseError => err
    $stderr.puts err.message
    $stderr.puts parser.help
    exit 1
  end

  keys = PublicKeyCryptosystem::RSA.make_key(bit_length)

  message = ""
  if message_file
    File.open(message_file, "rb") {|f|
      message = f.read() 
    }
  else
    message = STDIN.read() 
  end

  if message != keys[:private].decode(keys[:public].encode(message))
    $stderr.puts "rsa encrypton is broken."
    exit 1
  end

  sign = keys[:private].signature(message)
  if keys[:public].verify?(sign, message) != true
    $stderr.puts "digital signature is broken."
    exit 1
  end
  $stdout.puts "rsa encryption and rsa signature are running."
end

main

コマンド実行例

> ruby elgamalkeygen.rb --bits=1024 --public=public_key --private=private_key
> ruby elgamalencode.rb public_key < message_file | ruby elgamaldecode private_key | diff - message_file
> ruby digitalsignature.rb --bits=1024 < message_file

生成した1024bitのElGamal暗号の鍵の例

public_key_1024

--- !ruby/object:PublicKeyCryptosystem::ElGamal::PublicKey 
g: 121296486958969384930197694811581567108654703145467119337622260194797785277700923543849537033839638679285736554264100470527380830653704216480739459231693450853185625469099781323341612386833129138110507777238262827131187182404679749038074397890924265120547289683179357699026505173471876088465147475100354019166
p: 141451930331523386051653341311913273306092233328370587964756270766022988793924108831464134045680505951753325165721147729176922544377658954018237821872796888331275172664782824785569014046881803380294181814585916526718657473189402749715244485177480277653160469835344865412489959973892731685643395894696231732843
split_length: 1023
y: 4318888890312082967569844357485121052171996030716349816138769955784425799535497679896841570382173742040760149183879360872883743142664837816814965450354810695495320238770737707167231436868417592332467647912134733347007157298901184591920869769061779772182612478538448027597063901319404557075718978292562454341

private_key_1024

--- !ruby/object:PublicKeyCryptosystem::ElGamal::PrivateKey 
p: 141451930331523386051653341311913273306092233328370587964756270766022988793924108831464134045680505951753325165721147729176922544377658954018237821872796888331275172664782824785569014046881803380294181814585916526718657473189402749715244485177480277653160469835344865412489959973892731685643395894696231732843
split_length: 1023
x: 9976825294289580220861660681092361859863497994819211137267154454770652599773966014175750112864214316095752077219556363677153849255765879053312737438622741454845533086695216321914140859646225474674669249254490951941851692347532748460635175110091834950681438661188435630448082148366453045282304409192045431008

注意点

elgamalkeygenがものすごく遅いので注意してください。1024bitの鍵を作るのにPentiumM 1GHzで7時間くらい？かかりました。
鍵の長さを自由に指定できる(10とか。)ようにしたので暗号化や復号で面倒くさいことになっています。遅い原因のひとつ？っぽい

参考

• SICP p28 expmod
• Wizard Bible
• 青木日記 2007-03-29
• etc

修正

• ElGamal暗号で秘密鍵xの範囲を(0..p-2)から(1..p-1)に修正
• ElGamal暗号でrの範囲を(0..p-2)から(1..p-1)に修正