Bitcoin adopts public key cryptography for bitcoin exchange.
By knowing about algorism of public key cryptography,
easy to get understanding about private key and public key.
Now I'd like to talk about cryptography used some public key cryptography.
Public key cryptography
Public key cryptography is encryption method that encrypts and decrypts data using two keys paired.
A:public key A
B:public key B
It is a cryptography to implement Diffie-Hellman Key exchange concept.
Use public key to cryption or private key to decryption.
Easy to adminstration of keys and interoperable excellent system.
①Alice prepare key pair（Alice's private key, Alice's public key）,publishing public key(Alice's public key) to Bob.
②Alice have Bob encrypt sentence(Hello Alice!) with public key.
③Bob sends encrypted data(6EB6957008E03CE4) ,Alice decrypt the data with private key.
encryption:c = m^e mod R
decryption:m = c^d mod R
private key:d = d = e ^ − 1 ( mod ( p − 1 ) ( q − 1 ) )
e:Appropriate integer(public key)
※p,q is prime number
※e and R are relatively prime
※e < R
Greatest common divisor
def gcd(a, b): while b != 0: a, b = b, a%b return a
Least common multiple
def lcm(x, y): return x * y // gcd(x, y)
Use lcm and gcd to derive the "l".
Extended Euclidean Algorithm
def gcd2(x, y): c0, c1 = x, y a0, a1 = 1, 0 b0, b1 = 0, 1 while c1 != 0: m = c0 % c1 q = c0 // c1 c0, c1 = c1, m a0, a1 = a1, (a0 - q * a1) b0, b1 = b1, (b0 - q * b1) return c0, a0, b0
Euclidean algorithm calculate greatest common divisor of "a" and "b".
Furthermore expand to euclidean algorithm can find (x, y) that satisfies 「ax + by = gcd(a, b)」.
p,q = 50231, 89959 n = p * q l = lcm(p -1, q - 1) e = False while not gcd(e, l) == 1: e = random.randint(1,l) c, a, b = gcd2(e, l) d = a % l m = 20090103
Public key"e" is smaller than "l" and greatest common divisor of e and l is '1'.
Private key "d" finds from 「ed = 1(mod l) d」.
Above formula converte to「ex + ly = 1」.
Now,use the Extended Euclidean Algorithm to find x and find the private key d.
Since gcd 2 may take a negative value,so "a% l" calculate to take a positive number.
「a% l 」return "a" when "a" is positive,Add "l" when negative.
In the case ,subtract e from b, "ex + ly = 1" holds.
c = pow(m, e, n)
→Pow(built-in function) can describe 「c = m^e mod n」.
decryption = pow(c, d, n) print(decryption == m)
decryption = pow(c, d, n)
→Pow(m, e, n) means that describe「m = c^d mod n」too.
print(decryption == m)
→Return True when decryption data equal message"m". That means decryption success.
Bitcoin don’t use RSA , but Iｔ think that knowing the public key cryptography makes it easier to understand the concept of private key and public key.
The code used in this article is published in GitHub.