RSA encryption

In this series we will explore various cryptographic technologies that are relevant to cryptocurrency in general, and especially in increasing privacy and anonymity. This series lays the foundations and aims to help more people understand how anonymity can be achieved.

--

Small intro - Hi I'm Romano and I'm the lead developer of Viacoin. I posted this article on medium with the Viacoin account but I decided to still upload this on Steem (Yes I am also a Steem hodler myself) because more people will read this. I like to post quality articles and it would be waste to only let it stay on medium. So I aim to post quality articles, because let's be honst, a lot of articles on steem are terrible to read and seem very quickly written to make a buck or 2.

Old post link: https://medium.com/@viacoin/techology-primer-part-1-rsa-encryption-b98be35e189f

My Twitter: https://twitter.com/RNR_0

--

Digital signatures are used in the Viacoin & Bitcoin protocol. Viacoin & Bitcoin addresses are public keys and each of that public key corresponds to a private key. Public keys can be seen as a bank account number and private keys as the signatures to unlock the account.

A uses the private key to digitally sign a message to B. It’s important that her private key remains a secret. When the message has been signed it will be send to person B. The message is not encrypted but it’s authenticated thus B can verify the signature using A public key. If this is not the case, B can reject the message as invalid.

Now imagine if A wants to encrypt the message too. The message can have an arbitrary length, the solution is to first take a hash of the message and sign the hash. The output of the hash has always the same length. A digital signature protocol is the combination of the public key algorithm with a digital signature scheme.

RSA technology is not used by Viacoin & Bitcoin but will be very important to understand the upcoming anon feature. RSA is a non secret encryption and it’s a simple but great concept. Lock&unlock an inverse operation. A can encrypt her message and send her public key to B. No exchange in private keys are required. This means A can publish it on the internet and everyone can send A an encrypted message with only A who can decrypt it.

Introducing RSA

RSA makes use of one-way functions. It’s fast to encrypt but much slower to decrypt unless you have the information called a “Trapdoor”. Years ago Euclid showed every number has 1 prime factorization. This can be seen as a secret key. Prime factorization is fundamentally a hard problem because of time complexity. To generate a key A can create P which has a random big prime number (example over 200 digits) and after that a second random big prime number roughly the same size, call it Q. By multiplying these two primes together to get the number N. This multiplication takes the computer a few milliseconds. But if the gave N to someone else without telling P and Q the other person has to make his computer calculate for years to discover which numbers P and Q were.

The next step would be to Compute Euler’s Φ for n. This measures the break-ability of a number. Φ are the integers in the cyclic group 𝕫ₙ which are prime to n.

The trapdoor for solving Φ(n) = (P-1) * (Q-1)

Select an exponent e ∈ {1, …, Φ(n) -1} can be seen as Φ(n)¹⁰. Use exponent e as part of the public key. K as a random number.

Private key d = (K * Φ(n) +1) / e

The public key is (n, e) and the private key is d. Encryption is very simple. The cipher-text is m. m raised to the power of the public key e mod n. A long message m is just a long string of zeros and ones, thus can be interpreted as an integer.

c = mᵉ mod n
For decryption of c, it’s raised to the power of private key d modulo n.
m = cᵈ mod n

For encrypting a long message with RSA, n must be greater than m. As you can understand by now, private and public keys can be very big and the computational power can cost can become unbelievable large. To break RSA an attacker has to crack the unique prime factors of n.

The RSA signing scheme is similar to encryption. Signing can be done with raising the m digest x^d where x is the message and d the private key.

s = xᵈ mod n

To verify one has to raise the signature s to the power of the public key e and check for a match.

x = sᵉ = xᵉ*ᵈ = x mod n

RSA is the most widely used public key algorithm in the world. It strength rely on the hardness of prime factorization which is the result of deep questions about the distributions of prime numbers and this has been unsolved for thousands of years.

In the next part, we will cover Elliptic curve cryptography.