Module: Paillier::Primes

Defined in:
lib/paillier/primes.rb

Overview

:nodoc:

Constant Summary collapse

SmallPrimes = 
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Class Method Summary collapse

Class Method Details

.bitLength(int) ⇒ Object 



9
10
11
 
# File 'lib/paillier/primes.rb', line 9

def self.bitLength(int)
	return int.to_s(2).length
end

.generateCoprime(bits, coprime_to) ⇒ Object 



80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/paillier/primes.rb', line 80

def self.generateCoprime(bits, coprime_to)
	if( bits < 8 )
		raise "Bits less than eight!"
	end

	# If we find a number not coprime to n then finding `p` and `q` is trivial.
	# This will almost never happen for keys of reasonable size, so if
	# `coprime_to` is big enough we won't bother running the expensive test.
	no_test_needed = false
	if( coprime_to > (2 ** 1024) )
		no_test_needed = true
	end

	while( true )
		lowerBound = (2 ** (bits-1) + 1)
		size = ((2 ** bits) - lowerBound)
		possible = (lowerBound + SecureRandom.random_number(size)) | 1
		if no_test_needed or isCoprime?(possible, coprime_to)
			return possible
		end
	end
end

.generatePrime(bits, k = 50) ⇒ Object

Get a random prime of appropriate length



66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/paillier/primes.rb', line 66

def self.generatePrime(bits, k=50)
	if( bits < 8 )
		raise "Bits less than eight!"
	end
	while( true )
		lowerBound = (2 ** (bits-1) + 1)
		size = ((2 ** bits) - lowerBound)
		possible = (lowerBound + SecureRandom.random_number(size)) | 1
		if isProbablyPrime?(possible, k)
			return possible
		end
	end
end

.isCoprime?(p, q) ⇒ Boolean

Expensive test to prove coprimality. If GCD == 1, the numbers are coprime

Returns:

  • (Boolean) 


58
59
60
61
62
63
 
# File 'lib/paillier/primes.rb', line 58

def self.isCoprime?(p, q)
	while(q > 0)
		p, q = q, p % q
	end
	return (p == 1)
end

.isProbablyPrime?(possible, k = 50) ⇒ Boolean

Returns:

  • (Boolean) 


40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
 
# File 'lib/paillier/primes.rb', line 40

def self.isProbablyPrime?(possible, k=50)
	if( possible == 1 )
		return true
	end
	for i in SmallPrimes
		if( possible == i )
			return true
		elsif( possible % i == 0 )
			return false
		end
	end
	# This isn't a known prime number, so we'll check for primality
	# probabilistically
	return probabilisticPrimeTest(possible, k)
end

.probabilisticPrimeTest(target, k = 50) ⇒ Object

This is an implementation of the Rabin-Miller primality test. Previous versions used Little Fermat, but that is not effective in all cases; specifically, it can be thwarted by Carmichael numbers. We use 50 rounds as the default, in order to get a certainty of 2^-100 that we have found a prime. This implementation is adapted from rosettacode.org/wiki/Miller-Rabin_primality_test#Ruby



19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
# File 'lib/paillier/primes.rb', line 19

def self.probabilisticPrimeTest(target, k=50)
    d = target-1
    s = 0
    while d % 2 == 0
        d /= 2
        s += 1
    end
    k.times do
        a = 2 + rand(target-4)
        x = a.to_bn.mod_exp(d, target)
        next if x == 1 || x == target-1
        (s - 1).times do
            x = x.to_bn.mod_exp(2, target)
            return false if x == 1
            break if x == target - 1
        end
        return false if x != target-1
    end
    return true # probs prime
end