How Public Key Cryptography Works?
Introduction
Public Key Cryptography, or Asymmetric Cryptography, is a cryptographic system that uses two pairs of keys: Public Key and Private Key. This is one of the most important part of cryptocurrency protocols, and it is used in several places: crypto wallet creation, to ensure that crypto coins can only be spent by owners, signing of transactions (digital signature).These are the core components of cryptocurrency protocols. In short, if you send cryptocurrencies to others you sign that transaction using your private key (or signature key generated from using a private key) and the transaction is verified using your public key. So, if hackers obtain your private key, they would be able to send your cryptocurrencies to themselves.
There are a couple of algorithms to generate public and private keys. For example, Bitcoin protocol uses Elliptic-Curve Cryptography (ECC) and Elliptic Curve Digital Signature Algorithm (ECDSA) for digital signature. In this article I am going to explain Rivest–Shamir–Adleman (RSA) and compare it with ECC. RSA is one of the first and most widely used public key cryptosystems. It is named after its founders, Ron Rivest, Adi Shamir, and Leonard Adleman and it has become almost synonymous with public key cryptography.
RSA Algorithm
RSA makes extensive use of arithmetic operations using modulo-n (mod n) arithmetic. x mod n simply means the remainder of x when divided by n.
For example, 17 mod 5 = 2.
In general, RSA consists of three major parts (sometimes it makes sense to add public key sharing):
- Generate the public key and the private key
- Encrypt data using generated public key
- Decrypt data using generated private key
Generate the public key and the private key
To generate the public and private RSA keys, Alice or/and Bob (two fictional characters who have become the industry standard for discussions about cryptography) would perform the following steps:
- Choose two large prime numbers, p and q. The larger the values, the more difficult it is to break RSA, but the longer it takes to perform the encoding and decoding.
- Compute n = pq and z = (p — 1)(q — 1).
- Choose a number e, less than n, that has no common factors, other than 1, with z or their greatest common divisor (gcd) equals 1, gcd(e, z) = 1. In this case, e and z are said to be relatively prime. e will be used in encryption.
- Find a number d, such that ed — 1 is exactly divisible by z. In another way ed mod z = 1. d will be used in decryption.
- The public key that Bob or Alice makes available to the world is the pair of numbers (n, e) and the private, which must be secret, is the pair of numbers (n, d).
Encrypt data using generated public key
Suppose Alice wants to send Bob a message, which is represented by bit pattern integer number m (plaintext message), where m < n. The encrypted value c (ciphertext) of plaintext message m is c = m^e mod n
Ciphertext c will be sent to Bob. Note that Alice encrypts the message using Bob’s public key.
Decrypt data using generated private key
To decrypt received ciphertext c Bob computes m = c^d mod n which requires use of his private key (n, d).
The security of RSA relies on the fact that there are no known algorithms for quickly factoring (prime factorization) a number. In this case the public value n into p and q.
RSA vs ECC
In ECC a private key is a randomly generated integer number. In Bitcoin protocol it is 256 bit
(32 bytes) integer number. A public key is calculated/derived from a private key using elliptic curve cryptography, but not vice versa and compressed public key size is 33 bytes. ECC can use the same algorithm but with different elliptic curves to generate a public key. Bitcoin protocol uses Secp256k1 and public keys are either compressed or uncompressed.
RSA keys (public, private and signature) are big and key generation is slow.
On the other hand, RSA is easy to implement, while ECC is difficult to properly implement. In December 2010, PlayStation 3 was hacked, because Sony did not properly implement the algorithm. This is why it is recommended to use already tested libraries like OpenSSL to generate ECC key pairs.
About a year ago I implemented an open source library called eccpem and put it on GitHub, which generates ECC key pairs and stores them on the .pem files using OpenSSL library.
Conclusion
Most cryptocurrency protocols use ECC & ECDSA instead of RSA. There are at least two reasons:
- ECC uses much less memory than RSA, which is important in crypto protocols.
- ECC is faster than RSA.
Q: Which one is a secure algorithm?
A: They both are secure for now.
