# Introduction

The purpose of this
paper is to emphasize in the importance of cryptography, focus in RSA
asymmetric cryptographic algorithm and explain:

- What is cryptography

- Why cryptography is important

- History of Cryptography

- Mathematical RSA operations

- How to perform an RSA brute-force

**What is Cryptography**

Cryptography (or cryptology; from Greek κρυπτός, kryptos, "hidden, secret"; and γράφω, gráphō, "I write", or -λογία, -logia, respectively) is the practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer science, and engineering. Applications of cryptography include ATM cards, computer passwords, and electronic commerce. [2]

Until recently
cryptography referred mostly to encryption, which is the process of converting
ordinary information (plaintext) into unintelligible gibberish (i.e. cipher-text).
[4] Decryption
is the reverse, in other words, moving from unreadable cipher-text back to
plaintext. A cipher is a pair of algorithms that create the encryption and the
reversing, also called decryption. [4] The
operation of an algorithmic cipher is controlled by both the algorithm and in
each instance by a key. The key is a secret parameter (ideally known only to
the communicants) for a specific message exchange context. [4]

In order
for two parties to exchange a cryptographic message both must have one or two
secret keys (it depends if the parties use an asymmetric or a symmetric
algorithm) and a known mathematical cryptographic algorithm (both parties must
know the details of the cryptographic algorithm) the following diagram shows
the process.

**Picture2**: Simple encryption decryption operation (if the cryptography used is symmetric then key1=key2) [3]

**Note**: Secret keys are very important, as ciphers without variable size keys can be trivially broken with only the knowledge of the cipher used and are therefore not useful at all in most cases.

**History of Cryptography**

Before the modern era, cryptography was concerned solely with message confidentiality (i.e., encryption) — conversion of messages from a comprehensible form into an incomprehensible one and back again at the other end, rendering it unreadable by interceptors or eavesdroppers without secret knowledge (namely the key needed for decryption of that message). Encryption was used to (attempt to) ensure secrecy in communications, such as those of spies, military leaders, and diplomats. [6]

The earliest forms of secret writing required little more than local pen and paper analogy, as most people could not read. More literacy, or literate opponents, required actual cryptography. The main classical cipher types are transposition ciphers, which rearrange the order of letters in a message (e.g., 'hello world' becomes 'ehlol owrdl' in a trivially simple rearrangement scheme), and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters (e.g., 'fly at once' becomes 'gmz bu podf' by replacing each letter with the one following it in the Latin alphabet). [6]

Cryptography consists from two main categories (some people might claim more categories but for the papooses of this paper two categories cover the needs of this paper). The fist category is symmetric cryptography and the second category is asymmetric cryptography.

Plaintext = Decryption ( k , Cipher ) = Decryption ( k , Encryption ( k , Plaintext )) (3)

#
Asymmetric
Cryptography

Unlike Symmetric Cryptography, Asymmetric Cryptography uses a different key for encryption than for decryption. I.e., a user knowing the encryption key of an asymmetric algorithm can encrypt messages, but cannot derive the decryption key and cannot decrypt messages encrypted with that key. This difference is the most obvious difference of Symmetric and Asymmetric Cryptography. Another difference of Symmetric and Asymmetric Cryptography is the mathematical properties of each type of algorithm and they way the mathematical algorithm is implemented in a hardware or software device (further explanation of these differences are out of the scope of this paper).

The RSA Cryptographic algorithm is being exploited by a company named also RSA. The company RSA is the security division of EMC (EMC acquired RSA for its security products in 2006). RSA Laboratories is the research center of RSA, The Security Division of EMC, and the security research group within the EMC Innovation Network. The group was established in 1991 at RSA Data Security, the company founded by the inventors of the RSA public-key cryptosystem. Through its applied research program and academic connections, RSA Laboratories provides state-of-the-art expertise in cryptography and data security for the benefit of RSA and EMC. [10]

Represented by the equation "c = me mod n," the RSA algorithm is widely considered the standard for encryption and the core technology that secures the vast majority of the e-business conducted on the Internet. The U.S. patent for the RSA algorithm (# 4,405,829, "Cryptographic Communications System And Method") was issued to the Massachusetts Institute of Technology (MIT) on September 20, 1983, licensed exclusively to RSA Security and expires on September 20, 2000. [9]

For nearly two decades, more than 800 companies spanning a range of global industries have turned to RSA Security as a trusted, strategic partner that can provide the proven, time-tested encryption implementations and resources designed to speed time to market. These companies, including nearly 200 so far in 2000, rely on RSA BSAFE® security software for its encryption implementation and value-added services for a broad range of B2B, B2C and wireless applications. [9]

The RSA algorithm involves the three following steps:

Very simplistically talking, it means that the remainder of the division of a prime number with any integer besides 1 and itself should be 0!!

The first fifteen prime numbers are:

This is
often computed using the extended Euclidean algorithm [12] (Euclidean algorithm
is out of the scope of this paper).

In mathematical jargon, we say that d is the multiplicative inverse of e modulo φ [15]. The value of d is to be kept secret. If you know the value of φ, the value of d can be easily obtained from e using a technique known as the Euclidean algorithm. If you know n (which is public), but not p or q (which have been destroyed), then the value of φ is very hard to determine. The secret value of d together with the value n represents the private key. The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.

#
RSA
Encryption

The security of the RSA cryptosystem is based on two mathematical problems:

###

The earliest forms of secret writing required little more than local pen and paper analogy, as most people could not read. More literacy, or literate opponents, required actual cryptography. The main classical cipher types are transposition ciphers, which rearrange the order of letters in a message (e.g., 'hello world' becomes 'ehlol owrdl' in a trivially simple rearrangement scheme), and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters (e.g., 'fly at once' becomes 'gmz bu podf' by replacing each letter with the one following it in the Latin alphabet). [6]

**Asymmetric and Symmetric Cryptography**Cryptography consists from two main categories (some people might claim more categories but for the papooses of this paper two categories cover the needs of this paper). The fist category is symmetric cryptography and the second category is asymmetric cryptography.

**Symmetric Cryptography**

Symmetric Cryptography uses cryptographic algorithms that use identical cryptographic keys for both decryption and encryption (this is not entirely true, but again for the purposes of this paper we accept it as a fact).The Symmetric Cryptography keys, in practice, represent a shared secret between two or more parties that can be used to maintain a private information link. [5] The following simple mathematical relationships can describe the relation between decryption and encryption in Symmetric Cryptography.

Encryption ( k , Plaintext ) = Cipher (1)

Decryption ( k , Cipher ) = Plaintext (2)

Encryption ( k , Plaintext ) = Cipher (1)

Decryption ( k , Cipher ) = Plaintext (2)

Where k a secret shared value and Plaintext the data input we want to convert into cipher. From relationships (1) and (2) we can conclude that:

Plaintext = Decryption ( k , Cipher ) = Decryption ( k , Encryption ( k , Plaintext )) (3)

**Note**: Among the most popular and well-respected symmetric algorithms ARE Twofish, Serpent, AES (Rijndael), Blowfish, CAST5, RC4, TDES, and IDEA.

**Picture3**: Symmetric cryptography [7]

#
Asymmetric
Cryptography

Asymmetric Cryptography
also known as Public key cryptography is a cryptographic category which
involves the use of asymmetric cryptographic key algorithms.The asymmetric key
algorithms are used to create a

**mathematically related key pair: a secret private key and a published public key.**[6]
The following simple
mathematical relationships can describe the relation between decryption and
encryption in Asymmetric Cryptography.

Encryption ( k1 , Plaintext ) = Cipher (4)

Decryption ( k2 , Cipher ) = Plaintext (5)

Where k2 a secret non shared value, k1 a non secret shared value and Plaintext the data input we want to convert into cipher. From relationships (4) and (5) we can conclude that:

Plaintext = Decryption ( k2 , Cipher ) = Decryption ( k2 , Encryption ( k1 , Plaintext )) (6)

In relationship we can realize that the decryption of the Plaintext is a more complex relationship that is dependents to both keys to be used.Public key cryptography is used widely. It is the approach which is employed by most cryptosystems. It underlies such Internet standards as Transport Layer Security (TLS), PGP, and GPG.The most famous asymmetric algorithm is RSA. In cryptography, RSA (which stands for Rivest, Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography. RSA is widely used in electronic commerce, and is believed to be secure when proper secret keys are used.

Encryption ( k1 , Plaintext ) = Cipher (4)

Decryption ( k2 , Cipher ) = Plaintext (5)

Where k2 a secret non shared value, k1 a non secret shared value and Plaintext the data input we want to convert into cipher. From relationships (4) and (5) we can conclude that:

Plaintext = Decryption ( k2 , Cipher ) = Decryption ( k2 , Encryption ( k1 , Plaintext )) (6)

In relationship we can realize that the decryption of the Plaintext is a more complex relationship that is dependents to both keys to be used.Public key cryptography is used widely. It is the approach which is employed by most cryptosystems. It underlies such Internet standards as Transport Layer Security (TLS), PGP, and GPG.The most famous asymmetric algorithm is RSA. In cryptography, RSA (which stands for Rivest, Shamir and Adleman who first publicly described it) is an algorithm for public-key cryptography. RSA is widely used in electronic commerce, and is believed to be secure when proper secret keys are used.

**Picture4**: Asymmetric cryptography [7]

**Asymmetric and Symmetric Cryptography revised**

Unlike Symmetric Cryptography, Asymmetric Cryptography uses a different key for encryption than for decryption. I.e., a user knowing the encryption key of an asymmetric algorithm can encrypt messages, but cannot derive the decryption key and cannot decrypt messages encrypted with that key. This difference is the most obvious difference of Symmetric and Asymmetric Cryptography. Another difference of Symmetric and Asymmetric Cryptography is the mathematical properties of each type of algorithm and they way the mathematical algorithm is implemented in a hardware or software device (further explanation of these differences are out of the scope of this paper).

**Why RSA is important**

The RSA Cryptographic algorithm is being exploited by a company named also RSA. The company RSA is the security division of EMC (EMC acquired RSA for its security products in 2006). RSA Laboratories is the research center of RSA, The Security Division of EMC, and the security research group within the EMC Innovation Network. The group was established in 1991 at RSA Data Security, the company founded by the inventors of the RSA public-key cryptosystem. Through its applied research program and academic connections, RSA Laboratories provides state-of-the-art expertise in cryptography and data security for the benefit of RSA and EMC. [10]

Represented by the equation "c = me mod n," the RSA algorithm is widely considered the standard for encryption and the core technology that secures the vast majority of the e-business conducted on the Internet. The U.S. patent for the RSA algorithm (# 4,405,829, "Cryptographic Communications System And Method") was issued to the Massachusetts Institute of Technology (MIT) on September 20, 1983, licensed exclusively to RSA Security and expires on September 20, 2000. [9]

For nearly two decades, more than 800 companies spanning a range of global industries have turned to RSA Security as a trusted, strategic partner that can provide the proven, time-tested encryption implementations and resources designed to speed time to market. These companies, including nearly 200 so far in 2000, rely on RSA BSAFE® security software for its encryption implementation and value-added services for a broad range of B2B, B2C and wireless applications. [9]

**Math’s behind RSA**

The RSA algorithm involves the three following steps:

- Key generation.
- Encryption.
- Decryption.

**Note:**This is a simplistic approach of RSA.

**RSA Key generation**

# RSA includes a public key and a private key. The public key can be known to everyone and is used for encrypting messages. Messages encrypted with the public key can only be decrypted using the private key. The keys are generated the following way:

1.
Choose
two distinct

**prime numbers***p*and*q*. In mathematics, a**prime number**(or a**prime**) is a natural number that has exactly two*distinct*natural numbers 1 and itself. That means that a prime number can only be divided by 1 and itself: [13]**Example 1**: 5/5 = 1

**Example 2**: 5/1 = 5

Very simplistically talking, it means that the remainder of the division of a prime number with any integer besides 1 and itself should be 0!!

**Example 3**: 5/2 = 2, 5 (2, 5 is not an integer)

The first fifteen prime numbers are:

**Example 4:**2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

**Note:**For security purposes, the integer’s

*p*and

*q*should be chosen uniformly at random and should be of similar bit-length. [8]

2.
Compute

*n*=*pq**(a), where**n*is used as the modulus for both the public and private keys. For the purposes of this paper we will not use long secure integers. (as soon as we have the values n and φ, the values p and q will no longer be useful to us).**Note**: For the algebra to work properly, these two primes must not be equal. To make the cipher strong, these prime numbers should be large, and they should be in the form of arbitrary precision integers with a size of at least 1024 bits (bits are used when cryptography is applied in real life examples).

Example
3: (a)

**(b)***n*=*pq***which means that if p = 2 and q = 3 then n = 2*3 = 6 (both 2 and 3 are prime based in Example 4).**
Now that we have the values n and φ, the values p and q will no
longer be useful to us. However, we must ensure that nobody else will ever be
able to discover these values. Destroy them, leaving no trace behind so that
they cannot be used against us in the future. Otherwise, it will be very easy
for an attacker to reconstruct our key pair and decipher our cipher text.

3.
Compute

*φ*(*pq*) = (*p*− 1)(*q*− 1) (c) or*φ*(n) = (*p*− 1)(*q*− 1). (*φ*is Euler's totient function [11], Euler's totient function is out of the scope of this paper).
4.
Choose
an integer

*e*such that:
·

**1 <***e*<*φ***(***pq*)**or**
·

**1 <***e*<*φ***(***n*) or
·

**1 <**(d)*e*<*(p − 1) (q − 1)*
And

*e*and*φ*(*pq*) have no common divisors other than 1. We randomly select a number e (the letter e is used because we will use this value during encryption) that is greater than 1, less than φ, and relatively prime to φ. Two numbers are said to be relatively prime if they have no prime factors in common. Note that e does not necessarily have to be prime.
The value
of e is used along with the value n to represent the public key used for
encryption.

·

*e*is released as the public key exponent
5.
Determine

*d*(using modular arithmetic) which satisfies the relation:
·

*d*is kept as the private key exponent.**Note**: To calculate the unique value d (to be used during decryption) that satisfies the requirement that, if d * e is divided by φ, then the remainder of the division is 1. The mathematical notation for this (as already described above) is d * e = 1(mod φ).

In mathematical jargon, we say that d is the multiplicative inverse of e modulo φ [15]. The value of d is to be kept secret. If you know the value of φ, the value of d can be easily obtained from e using a technique known as the Euclidean algorithm. If you know n (which is public), but not p or q (which have been destroyed), then the value of φ is very hard to determine. The secret value of d together with the value n represents the private key. The public key consists of the modulus n and the public (or encryption) exponent e. The private key consists of the modulus n and the private (or decryption) exponent d which must be kept secret.

#
RSA
Encryption

RSA
Cryptographic User A transmits his public key

**(**to RSA Cryptographic User B and keeps his private key secret*n*,*e*)**(d,**. RSA Cryptographic User B then wishes to send a secret integer*e*)**m**to RSA Cryptographic User A. He first turns**m**into an integer 0 <*m*<*n*by using an agreed-upon reversible procedure (only known to Users A and B). He then computes the cipher text*c*corresponding to: [9]**Note:**And the encryption is successful. User A is the only person that can decrypt the secret integer

*m.***RSA Decryption**

# RSA Cryptographic User A can recover m from c by using her private key exponent d by the following computation:

**Note:**Given

*m*, he can recover the original message

**m**by using the agreed-upon reversible procedure.

**RSA Encryption/Decryption Simple example**

For the purposes of
this paper we are going to use a very simple number example. Based on Example 4
we have to:

1.
Choose

**and***q = 47***. Based in mathematical relationship (b) is n = pq =>***q = 73***n = 3431**also from relationship (c) we conclude that:
(c) =>

*φ*(*pq*) = (*p*− 1)(*q*− 1) or*φ*(*n*) =*φ*(*pq*) =*φ*(*6*) = (73-1)(47-1) = 72*46 = 3312 =>*φ***= 3312**

2.
Now
that we have

*n*and*φ*, we should discard*p*and*q,*and destroy any trace of their existence.
3.
Next,
we randomly select a number

*e**, that**e*> 1 and*e*is coprime [16] to**3312**(which is*φ***)**. We choose*e = 425*
4.
Then
the modular inverse of

*e*is calculated to be the following:*d = 1769*
5.
We
now keep

*d*private and make*e*and*n*public.
6.
Assume
that we have plaintext data represented by the following simple number:

*Plaintext = 707*

7.
The
encrypted data is computed by

*c*=*m*(mod^{e}*n*) as follows:

*Cipher*

*text = 707^425(mod 3431) = 2142*
8.
The
cipher text value cannot be easily reverted back to the original plaintext
without knowing

*d*(or, equivalently, knowing the values of*p*and*q*). With larger bit sizes, this task grows exponentially in difficulty. If, however, you are privy to the secret information that*d*= 1769, then the plaintext is easily retrieved using*m*=*c*(mod^{d}*n*) as follows:

*Plaintext = 2142^1769(mod 3431) = 707***Why RSA can’t break**

The security of the RSA cryptosystem is based on two mathematical problems:

- The problem of factoring large numbers
- The RSA problem.

**integer factorization**or

**prime factorization**is the breaking down of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer. [17] In cryptography, the

**RSA problem**summarizes the task of performing an RSA private-key operation given only the public key. [18] Full decryption of an RSA cipher text is thought to be infeasible on the assumption that both of these problems are hard because no efficient algorithm exists for solving them.

**Appendix**

**C**

**Cryptography:**Is the process of converting ordinary information (plaintext) into unintelligible gibberish.

**Cipher:**Is unintelligible gibberish

**Coprime:**In mathematics, two integers

*a*and

*b*are said to be

**coprime**or

**relatively prime**if they have no common positive factor other than 1 or, equivalently, if their greatest common divisor is 1. [16]

**D**

**Decryption:**Is the reverse process of encryption

**M**

**Multiplicative inverse**: In mathematics, a

**multiplicative inverse**or

**reciprocal**for a number

*x*, denoted by

^{1}⁄

*or*

_{x}*x*

^{−1}, is a number which when multiplied by

*x*yields the multiplicative identity, 1. [15]

**P**

**Plaintext:**Is ordinary readable information

**Problem of factoring large numbers:**In number theory,

**integer factorization**or

**prime factorization**is the breaking down of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer. [17]

**Prime numbers:**In mathematics, a

**prime number**(or a

**prime**) is a natural number that has exactly two

*distinct*natural number divisors: 1 and itself. [13]

### References

**[2]:**Liddell and Scott's Greek-English Lexicon. Oxford University Press. (1984)