Ex 6. Following publication of the RSA algorithm it was decided that in order to

Question

Ex 6.

Following publication of the RSA algorithm it was decided that in order to test the security of the algorithm ‘a game’ was published in Scientific American. A public key was printed and a cipher text created using that public key. A $100 prize was offered for the first person to break the code and retrieve the plaintext. It took 17 years for that to happen. Although this was a long time, it showed that given enough time and manpower, the algorithm could be broken. Today, with immensely more powerful computers, it would have been broken much more easily.

It is believed that the most efficient way of breaking an RSA encrypted message is concerned with the factoring of large semi-primes. Hence further challenges were set by the RSA laboratories.

Do a literature search/web-search and briefly summarise the outcome of that challenge.

(Max: 1 page A4 with appropriate referencing.)

Ex 7. Perform your own literature search in order to investigate the factoring algorithms currently available which try to extract prime factors of large numbers.

These basically fall into two types: special purpose algorithms and general purpose algorithms. Write a summary of your findings (Max: 1 page A4 with appropriate referencing); choose one algorithm from your literature search that you believe to be particularly relevant to the factoring of numbers set by the RSA company to describe in greater detail (Max: 2 pages A4 with appropriate referencing).

Explanation / Answer

Ex 6 : RSA is an algorithm used by modern computers to encrypt and decrypt messages. It is an asymmetric cryptographic algorithm. This is also called public key cryptography, because one of them is public and can be given to everyone. The other key must be kept private. It is based on the fact that finding the factors of an integer is hard (the factoring problem).

Generalization of RSA algorithm

The entire RSA protocol is built from two large prime numbers. These prime numbers are manipulated to give a public key and private key. Once these keys are generated they can be used many times. Anyone can encrypt a message using the public key and sent it to the creator of the keys. This person then uses the private key to decrypt the message. Only the one possessing the private key can decrypt the message.

One of the special numbers generated and used in RSA encryption is the modulus, which is the product of the two large primes. In order to break this system, one must compute the prime factorization of the modulus, which results in the two primes. The strength of RSA encryption depends on the difficultly to produce this prime factorization.

The particular problem at work is that multiplication is pretty easy to do, but reversing the multiplication in the form of factoring is apparently pretty hard.

For example, 174778781876547 × 55427044345769 = ?

It can be computed in few minutes but if in turn the question is reversed and asked like

------- * --------- =387692049691263893746982363620

which is very difficult and this process is called factorization(done in RSA algorithm.

Cracking the algorithm

Although factorization seems like a very hard problem, there's a different problem that's much easier finding the greatest common divisor GCD of two numbers. This means the largest integer that both of the numbers are divisible by. In 2 cases gcd can be 1

There is a very ancient and very fast method for calculating gcd, even for extremely large numbers. One important fact about it is,, even though factorization seems very hard and slow, calculating gcd is very fast and easy. Suppose there are four different primes, a, b, c, and d. The first two are used in one key, in the public valuen1 = a × b. The other two are used in another key, in the public value n2 = c × d.Finally,n1 and n2 must be relatively prime to each other.

In this scenario, there are now only three different primes a, b, and c. Somehow, b has been re-used in two different keys, so the public values are n1 = a × b and n2 = b × c. In this case, the re-use of a prime number across keys turns out to be extremely significant, and extremely bad for the security of those keys.The security problem comes in if someone comes across both public keys and, looking at the public values n1 and n2, decides out of curiosity to calculate gcd(n1, n2). This time, the result is not 1, but rather b, because both n1 and n2 are evenly divisible by b.now it's easy to calculate a = n1 / b and c = n2 / b. That reveals both of the secret prime factors of both keys, which is enough to derive a complete private key for each and start decrypting encrypted messages.

Shor's algorithm could be used to break public-key cryptography schemes such as the widely used RSA scheme.

Ex 7: There are many reasons why mathematicians and computer scientists want to factor integers. The easiest way to compute arithmetic functions like ¢l(N), cr(N), deN), etc uses the factorization of N.

The different types of factoring algorithms are

The factoring algorithms could also be divided into 2 subgroups because of their specific purpose.

Examples : trial division, Fermat’s factorization method, Pollard’s p 1 algorithm and the elliptic curve method.

Examples: Dixon’s factorization method, the quadratic sieve and the general number field sieve

Dixon’s Factorization Method

Coming back to the ideas of Fermat’s algorithm, John Dixon came up with further improvements to the congruence of squares scheme. Some parts to this algorithm comes from the work of Morrison-Brillhart, which involves the use of linear algebra. The improvements made in this method comes of the work by MorrisonBrillhart , and begins by choosing a bound B and identifying the so called factor base. This means that we choose an integer B and calculate all primes less than B, which will be called our factor base (denote this P).

We then start looking for integers m such that Q(m) = m2 n can be expressed in terms of our factor base. This is equivalent to the equation: m2 i YP ai i (mod n). After finding a couple of these relations we can use the knowledge from linear algebra to multiply some of these relations together in a way that the product will be a congruent square.

m2 1 × m2 2 × ... × m2 k Y i P (ai,1+ai,2+...+ai,k) i (mod n), ------- 4

where the exponents ai,1 + ai,2 + ... + ai,k 0 (mod 2).

The reason for using modulo 2 in the exponent is because this would yield that every even number in the exponent would be 0, and every odd number would be 1. This indicates that if we could find a relation ai,1 + ai,2 + ... + ai,k 0 (mod 2), we would have find an proper square. If such a relationship is found, we have constructed our awaited congruence of squares 19 x 2 y 2 (mod n).

We finally compute GCD(x+y, n) or GCD(xy, n), which hopefully will yield our factorization. As stated in the section concerning Kraitchik, some solutions in this equality will not yield any significant result. If x ± y, then we would get the factorization n = n × 1. We would then have to search for a different linear combination such that equation (4) holds This algorithm uses a structured method to find the proper factorization

Example: Suppose that n = 1189. We decide to choose the factor base as {2, 3, 5, 7}, and we can start our data collection phase. We know that n 34.8. We then search for integers that could factor into our factor base, for instance

352 Q(35) 2 2 × 3 2 × 5 0 × 7 0 (mod 1189)

372 Q(37) 2 2 × 3 2 × 5 1 × 7 0 (mod 1189)

692 Q(69) 2 0 × 3 0 × 5 1 × 7 0 (mod 1189)

After finding some integers that satisfies our request, we look for a combination in which we can create a product where the exponents equal zero modulo 2. we have the exponent vectors

352 {2, 2, 0, 0} = {0, 0, 0, 0} (mod 2)

372 {2, 2, 1, 0} = {0, 0, 1, 0} (mod 2)

692 {0, 0, 1, 0} = {0, 0, 1, 0} (mod 2)

Looking for perfect squares, we can immediately see that 352 is a perfect square (exponent vector is 0 (mod 2)). We can then apply Fermat’s algorithm directly and receive that

1189 = 352 6 2 = (356)(35+ 6) = 29×41.

Using some linear algebra we note that combining 37 and 69 will also achieve an exponent vector that is 0 (mod 2). This translates to (69 × 37)2 = 2 2 × 3 2 × 5 2 , which can be rewritten as 25532 = 302 . This yields that 2553 30 (mod 1189), or 175 30 (mod 1189).

Finally we compute 1189 = GCD(175 30, 1189) × GCD(175 + 30, 1189) = 29 × 41.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.