Subscribed unsubscribe Subscribe Subscribe

Bitcoin blog

Essence of Bitcoin is innovation that may be related to remittance and asset holding rights and liberation and freedom

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

Diffie-Hellman key exchange
One of the common key cryptosystem,It's a method proposed to safely deliver keys.
Below code show about how to get common key by Alice and Bob.

def common_key(x, y):
    p = 13
    q = 53
    
    alice_send_bob = (y ** p) % x
    bob_send_alice = (y ** q) % x
    
    alice_common = (bob_send_alice ** p) % x
    bob_common   = (alice_send_bob ** q) % x
    return alice_common == bob_common

x = 8420449
y = 553
print(common_key(x, y))

①Create public key(x, y)and private key(p, q) ※x is prime number
②Encrypting public key by private key(alice_send_bob, bob_send_alice)
③Receive the encrypted data to each other , and decryption(alice_common, bob_common)
④Decrypted data of each other is same, Alice and Bob could get common key

Common key cryptosystem use same private key to cryption and decryption,so not practcal.

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 = (n*(P-1)*(Q-1)+1)/e

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

Consider to R (modulo:finite field(0-32)) multiplied by prime number P and Q as example.
①To encrypt plain text(m=7,13,17,24) to the power of public key(e=3)
②C (m to the power of e)is an encrypted ciphertext(13,19,29,30)
③For decryption, calculate c(cryption with public key e) to the power of d(private key "3")
④Then it can get plain text(self numbers "m" and blue lie).
f:id:adrenaline2017:20170328221756j:plain

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 the Euclidean Algorithm.
Greatest common divisor of "a" and "b" equal greatest common divisor factor of "a" and "a%b",
"a" is greatest common divisor of a and b when b=0.

Least common multiple

def lcm(x, y):
    return x * y // gcd(x, y)

using the value of greatest common divisor obtained by gcd.
Least common multiple of "a" and "b" is number obtained by dividing ”Common prime factors for "a" and "b" ” from the product of "a" and "b".


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)」.
a1x + b1y = c1...(2)
(1) - q(2) ...(3)
Repeat difference calculation until X=0(namely q=1),and then find x and y .

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(built-in function) can describe「m = c^d mod n」too.
print(decryption == m)
→Return True when decryption data equal message"m".That means decryption success.


The code used in this article is published in GitHub.