Public key cryptography

Overview
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.

Y=A^X(mod B)

Y:ciphertext
X:private key
A:public key A
B:public key B


RSA(cryptosystem)
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.

f:id:adrenaline2017:20170307122045p:plain

①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.


RSA algorithm
RSA cipher use to encrypt modular operation and nature of prime numbers.

encryption:c = m^e mod R
decryption:m = c^d mod R
private key:d = d = e ^ − 1 ( mod ( p − 1 ) ( q − 1 ) )

c:Ciphertext
m:Plaintext
e:Appropriate integer(public key)
R:p*q(public key)
d:private key

※p,q is prime number
※e and R are relatively prime
※e < R


RSA code
Now,Let's see how to calculate by RSA, while looking at the code.

Greatest common divisor

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

Using Greatest common divisor to derive the public key e.
Repeat assigning the value of "b" to "a" and the value of "a% b" to "b".
The value of "a" when "b = 0" is the greatest common divisor.

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)」.

Parameter

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.

Encryption

c = pow(m, e, n)

→Pow(built-in function) can describe 「c = m^e mod n」.

Decryption

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 It 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.