Public And Private Key Generation Algorithm

There are a couple of algorithms to generate public and private keys. For example, Bitcoin protocol uses Elliptic Curve Digital Signature Algorithm (ECDSA). In this article I am going to explain Rivest–Shamir–Adleman (RSA) and compare with ECDSA. RSA is one of the first and widely used public key cryptosystem. The private key is then used to generate the public key using a multiplication on an elliptic curve: The private key (K) will be multiplied by a point generator (G) located on the curve and the result will correspond to the public key (K), another point on the curve (or K = K.g).

May 13, 2019  Private Key Public Key; 1. Private key is faster than public key. It is slower than private key. In this, the same key (secret key) and algorithm is used to encrypt and decrypt the message. In public key cryptography, two keys are used, one key is used for encryption and while the other is. Key generation is the process of generating keys for cryptography. The key is used to encrypt and decrypt data whatever the data is being encrypted or decrypted.

Modern cryptographic systems include symmetric-key algorithms (such as DES and AES) and public-key algorithms (such as RSA). Symmetric-key algorithms use a single shared key; keeping data secret requires keeping this key secret. Public-key algorithms use a public key and a private key. The public key is made available to anyone (often by means of a digital certificate). A sender will encrypt data with the public key; only the holder of the private key can decrypt this data.

Since public-key algorithms tend to be much slower than symmetric-key algorithms, modern systems such as TLS and its predecessor SSL as well as the SSH use a combination of the two in which:

1. One party receives the other's public key, and encrypts a small piece of data (either a symmetric key or some data that will be used to generate it).
2. The remainder of the conversation (the remaining party) uses a (typically faster) symmetric-key algorithm for encryption.

The simplest method to read encrypted data is a brute force attack–simply attempting every number, up to the maximum length of the key. Therefore, it is important to use a sufficiently long key length; longer keys take exponentially longer time to attack, making a brute force attack invisible and impractical.

Currently, commonly used key lengths are:

1. 128-bits for symmetric key algorithms.
2. 1024-bits for public-key algorithms.

Key generation algorithms[changechange source]

In computer cryptography keys are integers. In some cases keys are randomly generated using a random number generator (RNG) or pseudorandom number generator (PRNG), the latter being a computeralgorithm that produces data which appears random under analysis. Some types the PRNGs algorithms utilize system entropy to generate a seed data, such seeds produce better results, since this makes the initial conditions of the PRNG much more difficult for an attacker to guess.

In other situations, the key is created using a passphrase and a key generation algorithm, using a cryptographic hash function such as SHA-1.

Related pages[changechange source]

• Distributed key generation: For some protocols no party should be in the sole possession of the secret key. Rather, during distributed key generation every party obtains a share of the key. A threshold of the participating parties need to work together in order to achieve a cryptographic task, such as decrypting a message.

References[changechange source]

In today’s electronic world where everything is done online, “trust” is hard to come by. Conversations can be snooped on, credit card numbers can be stolen, identities can be exchanged and unseen eyes are everywhere. Imagine business emails being maliciously read by competitors, company’s proposals being leaked and even crucial corporate information being tampered with…

This is where cryptography plays a crucial role, and important transactions have to be encrypted with strong algorithms to prevent leakage of information. We will discuss the basics of cryptography, public key cryptography, the RSA algorithm and the ‘PuTTYgen’ program (which is used to create and public and private keys) in this paper.

It is a commonly known fact that the field of cryptography involves two major models – the symmetric cipher model and the asymmetric cipher or public key cipher model. The major difference between the two models is that the symmetric cipher model uses the same key to encrypt and decrypt messages, and the asymmetric cipher model uses different keys for encryption and decryption. Some popular symmetric algorithms are DES (Data Encryption Standard), AES (Advanced Encryption Standard) and Blowfish. Similarly popular asymmetric cipher algorithms are RSA (which stands for Ron Rivest, Adi Shamir, and Leonard Adleman, who designed the algorithm), ElGamal and DSS (Digital Signal Standard).

Public Key Cryptography

The key concepts in public key cryptography are plain text, encryption algorithm, cipher text, decryption algorithm and the recovered text. In addition, we make use of the most important component of public key cryptography to encrypt and decrypt the text – the public and private keys. If one key is used to encrypt the text, the other key is used to decrypt the text. The public and private keys are mathematically connected. The public keys are normally managed by a trustworthy third party person. Some of the required features of public key cryptography are listed below:

1. The private key should be infeasible to be generated through the public key.
2. Both the private and public keys should be easy to generate.
3. Person ‘X’ (also popularly known as ‘Bob’) should easily be able to encrypt a message and send it to person ‘Y’ (also popularly known as ‘Alice’) using person ‘Y”s public key.
4. Similarly, person ‘Y’ should easily be able to decrypt the message using their private key.
5. A hacker should find it impossible to recover the original text in spite of knowing the ciphertext and the public key.

Public key cryptography solves two of the symmetric cipher model’s drawbacks:

1. The key distribution problem, which in the symmetric model is to figure a way to distribute the keys when a lot of people are involved. This is solved in the asymmetric model by having “key-value” pair.
2. The authentication problem (verifying that the message indeed came from where it should have come from), which is solved in the asymmetric key model by making use of “digital signatures”.

We will next see the RSA algorithm, which uses public key cryptography and is the basis of the PuTTYgen program.

RSA Algorithm

As already stated, ‘RSA’- stands for Ron Rivest, Adi Shamir and Leonard Adleman, who designed the algorithm. Most cryptographic algorithms involve tremendous amount of mathematics and the RSA algorithm is no exception. The mathematics behind the RSA algorithm are explained below in a lucid and easy to understand form. The basic idea behind the RSA algorithm is that it:

• “is a block cipher;
• it uses very large prime numbers for key generation; and
• the generated keys are mathematically linked.” (Walsh College, 2010)

There are three steps in the RSA algorithm:

1. generating the public and private keys
2. encrypting the message

We will see a brief gist of generating the public and private keys in this paper.

Generating the public and private keys:

1. For the RSA algorithm to be highly successful, two large prime numbers are chosen (‘u’ and ‘v’)
2. (n=u * v)

3. Totient of the product is calculated as:

Φ(n)= (u-1) (v-1) where ‘Φ’ is the Greek symbol ‘phi’.

4. Next, we need to find values for ‘P’ and ‘Q’ after which the two large prime numbers can be abandoned.

P * Q = 1(mod Φ(n))

The only condition here is that both ‘P’ and ‘Q’ must be relatively prime to Φ(n). Two numbers are relatively prime, if they have no common factors apart from 1.

For example,

GCD (15,10) = 5

GCD (18,10) =2

GCD (21, 10) = 1

Now, 21 and 10 are relatively prime to each other or co-prime to each other.

Step (d) seems to be a bit more complicated than it actually looks. This can be simplified and re-written, assuming ‘P’ to be 7:

7 * Q = K * Φ(n) + 1, where ‘K’ can be any number.

Now ‘P’ and ‘R’ are the public keys and ‘Q’ and ‘R’ become the private keys. (Prime Number Hide-and-Seek: How the RSA Cipher Works)

Explaining the RSA algorithm with an example:

1. We take two small prime numbers, 5 and 11, for this example.
2. “Φ(55) = (5 – 1) * (11 – 1) = 4 * 10 = 40.
3. Now, we need to find numbers (‘P’ and ‘Q’) to fit the equation:
P * Q = 1 (mod 40).
Now, ‘P’ and ‘Q’ must be relatively prime to 40. (Prime Number Hide-and-Seek: How the RSA Cipher Works)
4. If ‘P’ is considered as 7, and the unfamiliar modular mathematics are removed and replaced with a highly understandable equation,

7 * Q = K * 40 + 1,

We next consider ‘Q’ to be 23 which is the next prime number close to 40. ‘P’ and ‘Q’ should also not be congruent to mod 40.

The equation now becomes,

7 * 23 = 161

And ‘K’ now becomes ‘4’.

So, the primary keys are 7 and 55 and private keys are 23 and 55.

The RSA algorithm is tough to crack if the keys are long. RSA keys are typically between 1024 – 2048 bits long, and a key length of 1024 bits is mostly sufficient for most calculations.

Attacks against RSA:

There are four different types of attacks that are possible against the RSA algorithm.

1. Brute force: This is trying different types of combinations to crack the keys. It is very difficult to crack the algorithm when the keys are large.
2. Mathematical attacks: This is equivalent to factoring the two large primes, which again has not been successful.
3. Timing attacks: The timing attack depends on the running time of the decryption algorithm.
4. Chosen ciphertext attacks: This type of attack is aimed at the properties of the algorithm. (Stallings)

We will next move onto PuTTygen – a program for generating public and private keys.

PuTTY

“PuTTY is an SSH and telnet client, developed originally by Simon Tatham for the Windows platform. PuTTY is open source software that is available with source code and is developed and supported by a group of volunteers.” (Download PuTTY) It is used to generate public and private keys. The following screenshot shows the opening screen of the PuTTY program.

Public And Private Key Encryption

Before we move onto the other aspects of ‘PuTTYgen’ program, we will briefly divert to the topic of SSH. We can see from the above screenshot, that there are SSH-1 RSA and SSH-2 RSA and SSH2-2 DSA keys to generate. We will see a brief explanation of SSH next.

SSH

SSH is secure shell network protocol that is basically used to connect two networked computers securely. By means of SSH, the two computers can be used to perform remote and secure command login, secure data communication and other secure network services. SSH “connects, via a secure channel over an insecure network, a server and a client running SSH server and SSH client programs, respectively. The protocol specification distinguishes between two major versions that are referred to as SSH-1 and SSH-2.” (Secure Shell)

Retracing back to the PuTTY gen program, we can generate public and private keys by moving the mouse cursor constantly over the blank area.

The following screenshot shows the result of generating the public and private key pair:

As we can see, we have generated SSH-2 RSA keys of length 1024 bits. The public and private keys can be saved as .txt files for later use. If the keys are generated using a length of 2048 bits, security will be enhanced, but at the cost of decreased performance.

The ‘passphrase’ field is optional, but it is better used. It is used to encrypt the private key in case it falls into wrong hands. The use of passphrase is explained in the University of Waterloo website which states that the private key is like a debit card and the passphrase is the PIN that is used to guard it.

“With SSH private keys, if somebody manages to acquire it, they will not be able to use it until they’ve figured out your passphrase. A private key without a passphrase is like a credit card, once they acquire it they can immediately use it.” (SSH Public Key authentication)

Application of the keys generated:

The keys that are generated can be used for SSH authentication with OpenSSH. The public key is the one that will be stored on the server. The private key will be the key that will be stored on one’s own computer. Instead of using the traditional username and password to login, the SSH client will authenticate your private key with the public key which was stored on the server.

Public And Private Key Generation Algorithm Software

Conclusion

This paper discussed the basics of cryptography and the necessities of cryptography, followed by the public key cryptography. We next moved onto the mathematics behind the RSA algorithm and concluded with the PuTTY program, which is used to generate public and private keys. Using public and private keys for authentication may be the future for online login into various websites.

Bibliography