Here a new scheme of factorization � factorization using bit position and backtracking is implemented in two distinct ways. With this new method a certain kind of keys are proved unsafe in RSA implementation (which are not approaching attack from the remaining factorization algorithms), because they can be easily factored into their prime products by this algorithm.

back to contents

2. INTRODUCTION:

From that time, when man began to communicate with each other with meaningful languages and began to live in form of a society, government, there grows a necessity to hide several forms of data or information from unwanted persons. Classified data are needed to be exposed only to the related persons or authorities. Cryptography is the study of methods to disguise information so that only the intended recipients can obtain knowledge of its content. Today inventing secure and less costly cryptosystem invention is one of the challenges of the computer age and a large number of works are going on the remaining cryptosystems or inventing the new ones. This work is an evaluation of some unsafe keys in RSA cryptosystem implementation, the first public key cryptosystem of the world.

back to contents

3. FUNDAMENTALS OF CRYPTOGRAPHY:

Cryptography has a long and colorful history. Four groups of people have used and contributed to the art of cryptography: the military, the diplomatic corps, diarists, and lovers. Of these, the military has had the most important role and has shaped the field.

The messages to be encrypted, known as the plaintext, are transformed by a function that is parameterized by a key. The output of the encryption process, known as the cipher text. The art of breaking cipher is called cryptanalysis. The art of devising ciphers (cryptography) and breaking them (cryptanalysis) is collectively known as cryptology.

It will often be useful to have a notation for relating plaintext, cipher text, and keys. We will use

C=E_k (P)

To mean that the encryption of the plaintext P using key K gives the cipher text C. Similarly,

P=D_k(C)

represents of decryption of C to get the plaintext again. It then follows that

D_k (E_k (P))=P

The notation suggests that E and D are just mathematical functions, which they are. The only tricky part is that both are functions of two parameters, and we have written one of the parameters (the key) as a subscript, rather than as an argument, to distinguish it from the message.

A fundamental rule of cryptography is that one must assume that the cryptanalyst knows the general method of cryptography used. In other words, the cryptanalyst knows how the encryption method, E works. The amount of effort necessary to invent, test, and install a new method every time the old method is compromised or thought to be compromised has always made it impractical to keep this secret, and thinking it is secret when it is not does more harm than good.

This is where the key enters. The key consists of a relatively short string that selects one of many potential encryptions. In contrast to the general method, which may only be changed every few years, the key can be changed as often as required. Thus our basic model is a stable and publicity known general method parameterized by a secret and easily changed key.

The non-secrecy of the algorithm cannot be emphasized enough. By publicizing the algorithm, the cryptographer gets free consulting from a large number of academic cryptologists eager to break the system so they can publish papers demonstrating how smart they are. If many experts have tried to break the algorithm for 5 years after its publication and no one has succeeded, it is probably pretty solid.

The real secrecy is the key, and its length is a major design issue. Consider a simple combination lock. The general principal is that you enter digits in sequence. Everyone knows this, but the key is secret. A key length of two digits means that there are 100 possibilities. A key length of three digits means 1000 possibilities, and a key length of six digits means a million. The longer the key, the higher the work factor the cryptanalyst has to deal with. The work factor for breaking the system by exhaustive search of the key space is exponential in the key length. Secrecy comes from having a strong (but public) algorithm and a long key. To prevent ones kid brother from reading his email, 64-bit keys will do. To keep major governments at bay, keys of at least 256 bits are needed.

From the cryptanalyst�s point of view, the cryptanalysis problem has three principal variations. When he has a quantity of cipher text and no plaintext, he is confronted with the cipher text only problem. The cryptograms that appear in the puzzle section of newspapers pose this kind of problem becomes known plaintext problem. Finally, when the cryptanalyst has the ability to encrypt pieces of plaintext of own choosing we have the chosen plaintext problem. Newspaper cryptograms could be broken trivially if the cryptanalyst were allowed to ask such questions as: What is the encryption of ABCDE?

Novices in the cryptography business often assume that if a cipher can withstand a cipher text only attack, it is secure. This assumption is very native. In many cases the cryptanalyst can make a good guess at parts of the plaintext. For example, the first things many timesharing systems say when you call them up is �PLEASE LOGIN�. Equipped with some matched plaintext-cipher text pairs, the cryptanalyst�s job becomes much easier. To achieve security, the cryptographer should be conservative and make sure that the system is unbreakable even if his opponent can encrypt arbitrary amounts of chosen plaintext.

Encryption methods have historically been divided into two categories: substitution ciphers and transposition ciphers. We can classify the traditional cryptography into three parts. These are described bellow:

3.1 Substitution Ciphers:

In a substitution cipher each letter or group of letters are replaced by another letter or group of letters to distinguish it. One of the oldest known ciphers is the Caesar cipher, attributed to Julius Caesar. In this method, a becomes D, b becomes E, c becomes F and thus z becomes C. For example, attack becomes DWWDFN. In the examples, plaintext will be given in lowercase letters, and cipher text in uppercase letters.

At first glance this might appear to be a safe system because although the cryptanalyst knows the general system (letter for letter substitution), he does not know which of the 26! =4x10²⁶ possible keys are in use. In contrast with the Caesar cipher, trying all of them is not a promising approach. Even at 1msec per solution, a computer would take 10¹³years to try all the keys.

Nevertheless, given a surprisingly small amount of cipher text, the cipher can be broken easily. The basic attack takes advantage of the statistical properties of natural language. In English, for example, e is the most common letter, followed by t, o, a, n, i, etc. The most common two letters combinations or diagrams, are th, in, er, re, and an. The most common three letter combinations, or triagrams, are the, ing, and, and ion.

A cryptanalyst trying to break a monoalphabetic cipher would start out by counting the relative frequencies of all letters in the cipher text. Then he might tentatively assign the most common one to e and the next most common one to t. He would then look at triagrams, which strongly suggest that X is h. Similarly, if the pattern that occurs frequently, the Y probably stands for a. With this information, he can look for a frequently occurring triagrams of the form aZw, which is most likely to and. By making guesses at common letters, diagrams, and triagrams, and knowing about likely patterns of vowels and consonants, the cryptanalyst builds up a tentative plain text, litter by letter.

3.1 Transposition Ciphers:

The substitution ciphers preserve the order of the plaintext symbols but disguise them. Transposition ciphers, in contrast, reorder the letters do not disguise them. Figure.3-2 depicts a common transposition cipher, the columnar transposition. The cipher is keyed by word or phrase not containing any repeated letters. In this example, MEGABUCK is the key. The purpose of the key is to number the columns, column 1 being under the key letter closed to the start of the alphabet, and so on. The plaintext is written horizontally in rows. The cipher text is read out by columns, starting with the column whose key letter is the lowest.

To break a transposition cipher, the cryptanalyst must first be aware that he is dealing with transposition cipher. By looking at the frequency of E, T, A, O, I, N etc., it is easy to see if they fit the normal pattern for plaintext. If so, the cipher is clearly a transposition cipher, because in such a cipher every letter represents itself.

M	E	G	A	B	U	C	K
7	4	5	1	2	8	3	6
p	l	e	a	s	e	t	r
a	n	s	f	e	r	o	n
e	m	i	l	l	i	o	n
d	o	l	l	a	r	s	t
o	m	y	s	w	i	s	s
b	a	n	k	a	c	c	o
u	n	t	s	i	x	t	w
o	t	w	o	a	b	c	d

Figure: Example of Transposition Cipher.

3.1 One-time Pads

Constructing an unbreakable cipher is actually quite easy; the technique has been known for decades. First choose a random bit stream as the key. Then convert the plaintext into a bit string, for an example by using in its ASCII representation. Finally, compute the EXCLUSIVE OR of these two strings, bit by bit. The resulting cipher text cannot be broken, because every possible plaintext is an equally probable candidate. The cipher text gives cryptanalyst no information at all. In a sufficiently large sample of cipher text, each letter will occur equally often, as will every diagram and every trigram.

This method, known as the one-time pad, has a number of practical disadvantages, unfortunately. To start with, the key cannot be memorized, so both sender and receiver must carry a written copy with them. If either one is subject to capture, written keys are clearly undesirable. Additionally, the total amount of data that can be transmitted is limited by the amount of key available. If the spy strikes it rich and discovers a wealth of data, he may find himself unable to transmit it back to headquarters because the key has been used up. Another problem is the sensitivity of the method to lost or inserted characters. If the sender and receiver get out of synchronization, all data from then on will appear garbled.

3.2 Fundamental Cryptography Principles:

There are two principles underlying all of the cryptographic systems. The first principle is that all encrypted messages must contain some redundancy, that is, information not needed to understand the message, so that active intruder cannot send random junk and have it be interpreted as a valid message. However, adding redundancy also makes it much easier for cryptanalyst to break messages by tracing redundancies.

Thus cryptographic principle number one is that all messages must contain redundancy to prevent active intruders from tricking the receiver into acting on a false message. However, this same redundancy makes it much easier for passive intruders to break the system, so there is some tension here. Furthermore, the redundancy should never be in the form of n zeros at the start or end of message, since running such message through some cryptographic algorithms gives more predictable results, making the cryptanalyst�s job easier. A random string of English words would be a much better choice for the redundancy.

The second cryptographic principle is that some measures must be taken to prevent active intruders from playing back old messages. One such measure is including in every message a timestamp valid only for, say, 5 minutes. The receiver can then just keep repeating messages around for five minutes, to compare newly arrived messages to previous ones to filter out duplicates. Messages older than 5 minutes can be thrown out, since any replays sent more than 5 minutes later will be rejected as too old.

3.2 Secret-Key Algorithms:

Modern cryptography uses the same basic ideas as traditional cryptography, transposition and substitution, but its emphasis is different. Traditionally, cryptography have used simple algorithms and relied on very long keys for their security. Nowadays the reverse is true: the object is to make the encryption algorithm so complex and involved that even if the cryptanalyst acquires vast mounds of enciphered text of his own choosing, he will not be able to make any sense of it at all. There are a lot of secret key algorithms. In the bellow we will briefly discuss the most commonly used DES algorithm.

3.2. DES:

In January 1977, the U.S. government adopted a product cipher developed by IBM as its official standard for unclassified information. This cipher, DES (Data Encryption Standard), was widely adopted by the industry for use in security products. It is no longer secure in its original form, but in a modified form it is still useful. We will now explain how DES works.

An outline of DES is shown in Figure. 3-4(a). Plaintext is encrypted in blocks of 64-bits, yielding 64 bits of cipher text. The algorithm, which is parameterized by a 56-bit key, has 19 distinct stages. The first stage is a key independent transposition on the 64-bit plaintext. The last stage is the exact inverse of this transposition. The stage prior to the last one exchanges the leftmost 32 bits with the right most 32 bits. The remaining 16 stages are functionally identical but are parameterized by different functions or the key. The algorithm has been designed to allow decryption to be done with the same key as encryption. The steps are just run in the reverse order.

The operation of one of these intermediate stages is illustrated in Figure. 3-4(b). Each stages takes two 32-bit inputs and produces two 32-bit outputs. The left output is simply a copy of the right input. The right output is the bit wise EXCLUSIVE OR of the left input and a function of the right input and the key for this stage is K_i. All the complexity lies in the function.

The function consists of four steps, carried out in sequence. First, a 48-bit number, E, is constructed by expanding the 32-bit R_i-1according to a fixed transposition and duplication rule. Second, E and K_iare EXCLUSIVE ORed together. This output is then partitioned into eight groups of 6 bits each, each of which is fed into a different S-box. Each of the 64 possible inputs to an S-box is mapped onto a 4-bit output. Finally, these 8 x 4 bits are passed through a P-box.

In each of the 16 iterations, a different key is used. Before the algorithm starts, a 56-bit transposition is applied to the key. Just before each iteration, the key is partitioned into two 28-bit units, each of which is rotated left by a number of bits dependent on the iteration number. K_iis derived from this rotated key by applying yet another 56-bit transposition to it. A different 48-bit subset of the 56 bits extracted and permuted on each round.

Figure: The Encryption standard. (a) General outline. (b) Detail of one iteration.

3.2 Public-Key Algorithms:

Historically the key distribution problem has always been the week link in most cryptosystems. No matter how strong a cryptosystem was, if an intruder could steal the key, the system was worthless. Since all cryptographists always took for granted the encryption key and decryption key were the same (or easily derived from one another) and the key had to be distributed to all users of the system it seemed as if there was an inherent built-in problem: keys had to protected from theft, but they also had to be distributed, so they could not just be locked up in a bank vault.

In 1976, two researchers at Stanford University, Diffie and Hellman (1976), proposed a radically new kind of cryptosystem, called a public key cryptosystem is one which has the property that someone who knows only how to encipher (disguise) a piece of information cannot use the enciphering key to find the deciphering key without a prohibitively lengthy computation. This means that the information necessary to send private or secret messages, the enciphering algorithm along with the enciphering key, can be made public-knowledge by submitting them to a public directory. Ronald Revest, Adi Shamir and Leonard Adleman at MIT developed the first public-key cryptosystem, the RSA algorithm, in 1977.

We can summarize the terminology here. Public-key cryptography requires each user to have two keys: a public key, used by the entire world for encrypting messages to be sent to that user, and a private key, which the user needs for decrypting messages. We will consistently refer to these keys as the public and private keys, respectively, and distinguish them from the secret keys used for both encryption and decryption in conventional (also called symmetric key) cryptography.

back to contents

4. THE RSA CRYPTOSYSTEM:

RSA scheme is a �Public key cryptography,� developed by Ronald Rivest, Adi Shamir and Leonard Adelman in April 1977 [29] and is named after their names. Since that time, the algorithm has been employed in the most widely used Internet electronic communications encryption program, Pretty Good Privacy (PGP). It is also employed in both the Netscape Navigator and Microsoft Explorer web browsing programs in their implementations of the Secure Sockets Layer (SSL), and by Master card and VISA in the Secure Electronic Transactions (SET) protocol for credit card transactions.

4.1 Basic Uses of RSA Encryption:

The RSA Algorithm is only one implementation of the more general concept of public key cryptography, which permits two parties who have never met and who can only communicate on an insecure channel to nonetheless send secure and verifiable messages to each other.

4.2 The Arithmetic in the RSA System:

Typical encryption techniques use mathematical operations to transform a message (represented as a number or a series of numbers) into a cipher text. Mathematical operations called one-way functions are particularly suited to this task. A one-way function is one, which is comparatively easy to do in one direction but much harder to do in reverse. As a trivial example, it is comparatively easy to square a two-digit number; with a little concentration, many people can probably multiply 24 by 24 without using a pencil and paper. One the other hand, calculating the square root of the number 576 is much harder, even with a pencil and paper.

The RSA system uses one-way functions of a more complex nature. Specifically, the system uses modular arithmetic to transform a message (or pieces of the message, one piece at a time) into unreadable cipher text. Modular arithmetic is often called �clock� arithmetic, because addition, subtraction, and the like, work like telling time.

In the RSA encryption formula, the message (represented by a number M) is multiplied by itself (e) times (called �raising (M) to the power (e)�), and the product is then divided by a modulus (n), leaving the remainder as a cipher text (C):

C = M^e mod n

This is a hard operation to undo, when (n) is very large (200 digits or so), even the fastest computers using the fastest known methods could not feasibly recover the message (M) simply from knowing the cipher text (C) and the key used to create the message ((e) and (n)).

In the decryption operation, a different exponent, (d) is used to convert the cipher text back into the plain text:

C = M^d mod n

The modulus (n) is a composite number, constructed by multiplying two prime numbers, (p) and (q), together:

N = p * q

The encryption and decryption exponents, (d) and (e), are related to each other and the modulus (n) in the following way:

d = e^-1 mod ((p-1) (q-1))

To calculate the decryption key, one must know the numbers (p) and (q) (called the factors) used to calculate the modulus (n). When (n) is a sufficiently large number, it is infeasible, using known algorithms and the fastest computing techniques, to calculate the prime number factors of (n). In this project we tried to introduce a new algorithm to find out the prime number factors, that generates (n).

The RSA Algorithm may be divided, then, into three steps:

(1) Key generation: in which the factors of the modulus (n) the prime numbers (p) and (q) are chosen and multiplied together to form (n), an encryption exponent (e) is chosen, and the decryption exponent (d) is calculated using (e), (p), and (q).

(2) Encryption: in which the message (M) is raised to the power (e), and then reduced modulo (n).

(3) Decryption: in which the cipher text (C) is raised to the power (d), and then reduced modulo (n).

When the RSA Algorithm is used in a public key system, the modulus (n) and one of the exponents (arbitrarily, we can assume (e)) are published. The other exponent (d) is kept secret, as are (p) and (q), the factors of (n). The (p) and (q), the factors of (n) are not needed for encryption or decryption; they are only used in the key generation step (creating the modulus (n) and the second's exponent). In addition, while it is important for key generation purposes that the modulus (n) be the product of two prime numbers, the exponentiation and modular arithmetic operation would work just as well with prime numbers (which are by definition evenly divisible only by themselves and the number 1).

4.3 The RSA Algorithm:

In the RSA public key cryptosystem, a participant creates his public and private keys with the following procedure.

1. Select at random two large prime numbers p and q.

2. Compute n by the equation, n = p � q.

3. Compute z by the equation, z=(p-1) (q-1).

4. Select a small odd integer d that is relatively prime to z.

5. Compute e by the equation, e � d= 1 mod z

6. Publish the pair (e, n) as the RSA public key.

7. Keep secret the pair (d, n) as the RSA private key.

Then encryption and decryption are performed by the following rules:

If the message is M, encrypted message C = M^e mod n, and the decrypted message (original message) is found by M = C^d mod n.

4.4 Recent invention:

In 1998 Sarah Flannery of Ireland proposed a new algorithm of the RSA security, which is known as the Cayley-Purser algorithm. Its main properties are:

1. As secure as the RSA algorithm and

2. Faster than the RSA algorithm.

This algorithm uses (2*2) matrices. Plain text messages blocks are assigned numerical equivalents as in the RSA and placed four at a time in the four positions of a (2*2) matrix. This message matrix is then transformed into a cipher matrix by the algorithm and the corresponding cipher text is then extracted by reversing the assignment procedures used in the encipherment. Because this algorithm uses nothing more than matrix multiplication (modulo n) and not modular exponentiation as required by the RSA. It might be expected to encipher and decipher considerably faster than the RSA. It is found that the Cayley-Purser algorithm was approximately twenty two times faster than the RSA with respect to a 200-digit modulus.

back to contents

5. FACTORIZATION METHODS:

There is a remarkable disparity between the degree of difficulty of the task of multiplication and that of factorization. Multiplying integers together is a reasonable exercise for a young child if the integers are small, and it remains a very straightforward task even when the integers are very large. The reverse operation, however, that of resolving a given integer into factors, is cumbersome except for the very smallest integers and becomes near to impossible for large numbers. This asymmetry is exploited in RSA. In this system secrecy is provided by placing a would-be code breaker in a situation where in principle he commands all information necessary for reading the protected message but is confronted with an arithmetic task, which in practice is prohibitively time-consuming

Recent development in computational tools as well as the introduction of new concepts has made it possible to factor very large integers. Among the modern factorization methods the famous ones are Pollard�s (p+1) method, Shanks� Square Forms Factorization, Morrison and Brillhart�s Continued Fraction Method, Lenstra�s Elliptic Curve Method, Pollard�s Number field sieve and Montegomery�s Multiple Polynomial Quadratic Sieve Method.

In Pollard�s method the idea employed is that if p-1|Q then p|a^Q-1, if GCD (a, p)=1. First it may seem impractical but Pollard employed a technique that if p-1, for one of the factors p of N, happens to have a factorization containing only small prime factors, then if we compute GCD (a^Q-1, N) on these comparatively rare occasions, i.e., for those integers Q which have many prime factors, we might be able to determine p-1 (or a multiple thereof) rather soon, and thus find a relatively large factor p of N with a limited amount of work. In 1980 the researchers managed to discover the 16-digit factor of eighth Fermat number employing a couple of computer hour. Shanks� �square forms factorization� systematically applies the theory of binary quadratic forms (expressions of the form Ax²+Bxy+Cy²) to find factorization of integers. Morrison and Brillhart�s Continued Fraction Method employs the idea of finding a non-trivial solution to the congruence x²�y² mod N and then computing a factor p of N by means of Euclid�s algorithm applied to (x+y, N). In the years 1980-82, Thorkil Naur, worked with CFRAC and reported that computing time ranged from less than a hour for 35 digit number to about 24 hours for 45 digit numbers. The most difficult number reported was a 56-digit number, which took 35x24 hours to be factorized. Lenstra�s Elliptic Curve Method makes use of a group of rational points on an elliptic curve. In 1991 it was reported that ECM should require an effort of 10 hours to find 20-25 digit factors and a considerable effort to find 30-35 digit factors. It is also reported that years of combined effort of many researchers had resulted in hundreds and thousands of trials with ECM and they were able to find two 38 digit, one 37 digit and one 36 digit factors. The basic principle of Number Field Sieve is the same as for CRAFC, namely to find two congruent squares mod N. The difference is that the squares are formed not only from combining small rational numbers mod N, but also by combining small integers mod N in some cleverly chosen algebraic number field, the choice of which depends upon the number N to be factored. A.K.Lenstra, H.W.Lenstra, Jr., M.S. Manasse and J.M. Pollard have used NFS in 1990 to factor the ninth Fermat number. The job was distributed among 700 workstations around the world, running during the nighttime and it took a four-month labor. Montegomery�s MPQS is a sieving method that employs quadratic residues mod N. In April 1994 a version of MPQS was used by Arjen Lenstra and Derek Atkins to factor the so called RSA-129, a number that had been given in 1977 by the inventors of RSA encryption scheme as a challenge to computer scientists. The sieving was carried out in 8 months by about 600 volunteers, consuming estimated 5000 MIPS years.

All the methods described above show favor to special type of patterns and it is found that for many patterns our proposed method outperforms the existing ones.

back to contents

6. A NEW SCHEME - FACTORIZATION BY BACKTRACKING AND ITS APPLICATION TO FIND UNSAFE KEYS IN RSA IMPLEMENTATION:

Factoring large integers has redrawn the attention of researchers mainly after the RSA encryption technique has been proposed. Almost every method involving factorization requires expensive mod or division operations and they deal with the decimal representation of the number. The scheme invented by Enamul Karim and Shahidul Hasan (Dept. of computer Science, Dhaka University), avoids mod or division operations and deals with only the binary positions of a given number. The scheme details are sketched in the next algorithm part. The scheme use bit position to express binary numbers. Then the number is factorized by distributing its to two products and checking the validity of distribution by a simple cross addition operation. If any distribution fails then it backs to the previous stage by backtracking method using recursion. So this factorization scheme�s main points are-

1. It uses bit position to express binary numbers thus it can handle considerably large numbers.

2. It avoids mod or division calculation and uses only addition and the operation of incrementing, so less costly.

3. It uses recursive backtracking to find the correct prime products.

Now in this factoring method if the summing up action (see algorithm section) is barely needed or not needed then the distribution is very easy and the factorization of that number is gained with less effort. So if this pattern-type number is used in RSA implementation then the unsafe key can cause to insecurity. As for example, the prime products of 187 (10001111) are 11 (1011) and 23 (10111). If we express 187, 11 and 23 using bit position then respectively they are (0, 1,3,4,5,7), (0,1,3) and (0,1,2,4). The cross addition result of 11 (0,1,3) and 23 (0,1,2,4) are (0,1,3,4,5,7) �(0,1,3,4,5,7). From this example it is seen that the result of cross addition does not need any summing up action. So using the new factoring scheme the factorization of 187 (0,1,3,4,5,7) can be easily obtained.

back to contents

7. ALGORITHM OF THE PROGRAMS:

7.1 Key Words-

Expressing binary number by bit position- If 101001 is a binary number then its set bit positions are (positions that contain 1�s) 0^th, 3^rd and 5^th position. Then 101001 can be expressed with its set bit position, i.e. (0,3,5).

Cross addition- If every bit position of a number is added to every bit position of another number then this system is called cross addition. If we take 111(0,1,2) and 101(0,2) then the resulting cross addition is

(0+0, 0+1,0+2, 2+0, 2+1, 2+2) � (0, 1, 2, 2, 3, 4)

Summing up- In the result of cross addition if there exists one or more pairs of same element then the element is incremented by one, which is entered into the result as a new element and the previous pair is eliminated. Same process applied to as many as pairs found. From the previous reference, the sorted cross addition result of 111 and 101 is (0, 1, 2, 2, 3, 4). Then if we apply summing up the required steps are

(0, 1, 3, 3, 4) � (0, 1, 4, 4) � (0, 1, 5)

7.2.1 Program #1 (without bounding)

◈ Let suppose the input array is N and the resulting factor of N are P & Q arrays.

◈At first it ensured that N, P and Q array do not contain any garbage values other than zeroes by initializing them with zeroes.

◈ Then the input is converted into binary number (if it is not in binary). Then N is filled exactly with the bit-position of the binary number. Suppose if the input is 35 then its binary is (10011). So the set bit position is 0, 1 and 5. So the 0^th, 1^stand 5^th element of N array is filled up with one.

◈As the multiplication of two prime numbers must be an odd number so an input of even number is considered as an invalid input.

◈ Now the task is to distribute the entries of N one after one into P and Q and less them from N. Then check, if the distribution is valid by cross addition.

◈ As the input and resulting numbers are odd numbers, so 1 is placed at the 0^th element of P, Q and 0 is placed same to N without any calculation.

◈Now the value of every element of N is checked one after one and the following steps are taken according to their values.

◈ If in the examining element there found even number entry (including zero), then there are two possibilities- both P and Q have the bit or none of them. In case of odd number entry there are three possibilities- the bit may goes to P or Q or none.

◈ Whenever we set a bit in P or Q then we instantly cross add between their elements and check if the result of cross addition is found in N. If not then it would be obtained by breaking the next set bit. This operation is somewhat like reverse summing up. If N�s set bit position is 0, 1, 5 but the a cross addition result is found 3, but there is no set bit in position 3 in N. The next set bit is found in 5^th element. So its breaking phases to 2^nd position are (0, 1, 5) � (0, 1, 4, 4) � (0, 1, 3, 3, 4).

0	1	2	3	4	5
1	1	0	0	0	1

0	1	2	3	4	5
1	1	0	2	1	0

Figure: The condition of N before and after breaking the 5^th bit

◈ These operation one N, P and Q are processed by a recursive function. On processing if there is no one in array N then the output is shown and program terminates.

◈ There are some conditions by which the function takes decision to back to previous stage by recursion. In each stage the function works with a copy of the array N. So if there is a necessity to back to a previous stage an unaltered copy of N can be getting easily from the stack.

◈ For example the reverse summing up action is not allowed to the position, one less than the rightmost position. In the same way we can less a bit from that position if and only if in that time only one bit exists in N. Also if any cross addition result crosses the rightmost bit position in N, then it is obvious that the cross addition fails.

◈ After all possible matches if two product P & Q is not found then the program terminates.

7.2.2 Program #2 (with bounding)

◈ The main engine of this program is same to the program#1.

◈ By observation it is seen that if the MSB position of P, Q and N are P_L, Q_L and N_L, then one of the following equations must be true,

P_L + Q_L = N_L

P_L + Q_L = N_L � 1

◈ In this program at first various combinations of P_L and Q_L are taken by looping and then the previous operations are performed. So at the beginning bits are set in P_L and Q_L, and necessary bits are subtracted from the array N.

◈ As in this program the program flow have to come to the main function for taking various P_L and Q_L combination, so the process recursive function is used here with return type. Whenever a particular combination of P_L and Q_L failed then the process function back to the main function by successive returning zeroes.

◈ In this case each time of cross addition, the cross addition with P_L and Q_L is included. As the cross addition of P_L and Q_L is included every time so whenever the turn of P_L and Q_L come then only the cross addition with the opposite bit is included.

◈ If we let Q_L> P_L then after crossing the P_L position no bit can be set in array P.

◈ If the considering stage or bit position exceeds Q_L and there are still ones in the array N, then it is obvious that the combination fails.

◈ In array N in the same index of P_L or Q_L, if there found even or odd number entry then it should be treated in an opposite manner than the normal. Because from that index of N already one or two bits are subtracted for P_L and Q_L.

◈ When the stage came to P_Lor Q_L then it is not needed to less any bit from N for P_Lor Q_L, because at the beginning bits are less from N for them.

back to contents

8. PROGRAM CODING PHASE:

/* PROJECT: CRYPTOGRAPHY

Finding unsafe keys in RSA implementation

through the use of a new factoring scheme */

#include <stdio.h>

#include <conio.h>

#include <stdlib.h>

#include<math.h>

#include <dos.h>

#include <graphics.h>

const MAX = 200;

/* P and Q contains the multiplicands and N contains the number */

int P[MAX], Q[MAX], N[MAX];

int n; /* number of bits used */

int m; /* the position of the rightmost 1 in N */

int ones; /* number of 1's remaining in N */

long int count; /* number of checks needed */

int sign; /* flag set 1 if the program successful */

int skip = 0; /* determine whether intro is skiped */

int input(void);

void initialize(void);

unsigned long int bintodes(int p[], int k);

int takemunir(int X[], int k, int *m, int *ones);

int processmunir(int k, int N[], int m, int ones,int l);

void without_boundings(void);

int takeone(int X[], int k, int *m, int *ones);

int process(int k, int N[], int m, int ones,int l, int hbp, int hbq);

void mainprogram(void);

void front(void);

void help(void);

int check(void);

void drawrec(int del, int kept);

int menu(void);

void end(void);

void main()

{

int c;

front();

clrscr();

for(;;)

{

fflush(0);

c = menu();

switch(c)

{

case 1:

mainprogram();

break;

case 2:

without_boundings();

break;

case 3:

help();

break;

case 4:

end();

exit(0);

break ;

}

//---------input function for both the program---------------

//---------Returns 0 if the input is even else return 1------

int input(void)

{

unsigned long int x;

int i;

printf("Enter number: ");

scanf("%lu", &x);

if (x%2 == 0)

{

printf("Invalid number...\n");

return 0;

}

i = ones = 0;

while (x!=0)

{

ones += N[i++] = x%2;

x /= 2;

}

n = i;

m = n-1;

return 1;

}

//----------initilize function for both programs------------

void initialize(void)

{

int i;

for (i = 0; i < n; i++)

P[i] = Q[i] = 0;

P[0] = 1;

Q[0] = 1;

}

//---Used by both program to show the decimal equivalent of the output--

unsigned long int bintodes(int p[], int k)

{

unsigned long int ans = 0, i;

for(i = 0; i <= k; i++)

if(p[i] == 1)

ans = ans + pow(2, i);

return ans;

}

//-----functions for the without boundings program-----------

int takemunir(int X[], int k, int *m, int *ones)

{

int i;

if (k > *m)

return 0;

if (X[k] > 0)

{

if ((X[k] == 1) && (k == *m) && (*m == n-2) && (*ones > 1))

return 0;

if (k == *m)

(*m)--;

X[k]--;

(*ones)--;

}

else

{

i = k + 1;

while (X[i] == 0)

i++;

if ((X[i] == 1) && (i == *m) && (*m == n-2))

return 0;

if (i == *m)

(*m)--;

X[i]--;

i--;

*ones += i - k;

while (i > k)

{

X[i]++;

i--;

}

X[k]++;

}

return 1;

}

int processmunir(int k, int N[], int m, int ones,int l)

{

int X[MAX], i;

count++;

for (i = 0; i < n; i++)

X[i] = N[i];

if (k>1)

{

for (i = 0; i < l; i++)

if (!takemunir(X, k-1, &m, &ones))

return 0;

if (P[k-1] == 1)

{

for (i = 1; i < (k-1); i++)

{

if (Q[i] == 1)

if (!takemunir(X, k+i-1, &m, &ones))

return 0;

}

if (Q[k-1] == 1)

{

for (i = 1; i < (k-1); i++)

{

if (P[i] == 1)

if (!takemunir(X, k+i-1, &m, &ones))

return 0;

}

if ((P[k-1]==1) && (Q[k-1]==1))

if (!takemunir(X, k+k-2, &m, &ones))

return 0;

}

if (ones==0)

{

printf("Found!\n");

for (i=0; i<n; i++)

printf("%2d", P[i]);

printf("\t(%lu)",bintodes(P,n));

printf("\n");

for (i=0; i<n; i++)

printf("%2d", Q[i]);

printf("\t(%lu)",bintodes(Q,n));

printf("\n");

printf("It took %ld checks.\n",count);

sign = 1;

return 1;

}

if (k == (n-1))

return 0;

if (X[k]%2 == 0)

{ /* even number of 1s */

/* here there are two possibilities, both having 1s or no 1s at all */

/* both ones */

P[k] = 1;

Q[k] = 1;

if(processmunir(k+1, X, m, ones,2 ))

return 1;

/* No ones */

P[k] = 0;

Q[k] = 0;

if(processmunir(k+1, X, m, ones, 0))

return 1;

}

else

{ /* odd number of 1s */

/* here there are two possibilities, both having 1s or no 1s at all */

/* give it to P */

P[k]=1;

Q[k]=0;

if(processmunir(k+1, X, m, ones, 1))

return 1;

/* give it to Q */

P[k]=0;

Q[k]=1;

if(processmunir(k+1, X, m, ones, 1))

return 1;

Q[k]=0;

}

void without_boundings(void)

{

char ch;

clrscr();

{

sign = 0;

if(input())

{

initialize();

N[0]=0;

ones--;

count = 0;

processmunir(1,N,m,ones,0);

}

if(!sign)

printf("\n This number cannot be factorized.");

printf("\n Press q to back to main menu or any other key to continue: ");

fflush(0);

ch = getchar();

} while(ch != 'q');

}

//--------functions for main program--------------------

int takeone(int X[], int k, int *m, int *ones)

{

int i, flag2 = 0;

if (k>*m)

return 0;

if (X[k]>0)

{

if (k == *m)

(*m)--;

X[k]--;

(*ones)--;

}

else

{

i = k + 1;

for(; i < n; i++)

if(X[i] != 0)

{

flag2 = 1;

break;

}

if(!flag2)

return 0;

if (i == *m)

(*m)--;

X[i]--;

i--;

*ones += i-k;

while (i > k)

{

X[i]++;

i--;

}

X[k]++;

}

return 1;

}

int process(int k, int N[], int m, int ones,int l, int hbp, int hbq)

{

int X[MAX];

int i, mithu, flag3 = 0, jolly, flag4, sami;

count++;

mithu = 2;

sami = 2;

jolly = 2;

flag4 = 0;

for (i = 0; i < n; i++)

X[i] = N[i];

if(k == 1)

{

P[hbp] = 1; /*set the highest bit position of P & Q */

Q[hbq] = 1;

takeone(X, hbp, &m, &ones);

takeone(X, hbq, &m, &ones);

}

if (k>1)

{ // if highest bit position of Q is

if((k-1) != hbq) //then it dosen't need to takeone

for (i = 0; i < l; i++)

{

if (!takeone(X, k-1, &m, &ones))

return 1;

if((k-1) == hbp)

break;

}

if((k-1) != hbp) //there is no need of internal crossadds

if (P[k-1] == 1) //for highest bit position of P & Q

{

for (i = 1; i < (k-1); i++)

{

if (Q[i] == 1)

if (!takeone(X, k+i-1, &m, &ones))

return 1;

}

if(!takeone(X, k+hbq-1, &m, &ones))

return 1;

//crossadds with hbp & hbq must be

} // included everytime

if((k-1) != hbq)

if (Q[k-1] == 1)

{

for (i = 1; i < (k-1); i++)

{

if (P[i] == 1)

if (!takeone(X, k+i-1, &m, &ones))

return 1;

}

if((k-1) <= hbp)

if(!takeone(X, k+hbp-1, &m, &ones))

return 1;

}

/* if k-1 = hbp then the elements crossadd with hbp included before,

so it is excluded here */

if((hbp == hbq) || (k-1) != hbp)

if ((P[k-1] == 1) && (Q[k-1] == 1))

if (!takeone(X, k+k-2, &m, &ones))

return 1;

if((hbp != hbq) && ((k-1) == hbp ))

sami = takeone(X, hbp+hbq, &m, &ones);

if(sami == 0)

return 1;

else if(sami == 1)

flag4 = 1;

}

if((k == hbp) && (hbp == hbq))

mithu = process(k+1, X, m, ones, 0, hbp, hbq);

if(mithu == 0)

return 0;

else if(mithu == 1)

return 1;

if (ones == 0)

{

printf("Found!\n");

for (i = 0; i < n; i++)

printf("%2d", P[i]);

printf("\t(%lu)",bintodes(P, n));

printf("\n");

for (i=0; i<n; i++)

printf("%2d", Q[i]);

printf("\t(%lu)",bintodes(Q, n));

printf("\n");

printf("It took %ld checks.\n",count);

sign = 1;

return 1;

}

for(i = k; i <= n-1; i++)

if(X[i] != 0)

{

flag3 = 1;

break;

}

if((!flag3) && (ones)) /* if all said & done, but still ones alive */

return 1; /* then back to the pavelion */

if (k == n-1)

return 1;

if((k > (hbq)) && (ones)) /*if the stage number exeeds hbq then back*/

return 1;

if((hbp != hbq) && (k == hbq))

jolly = process(k+1, X, m, ones, 0, hbp, hbq);

if(jolly == 0)

return 0;

else if(jolly == 1)

return 1;

if((((X[k]%2)==0)&&(k!=hbp)&&(k!=hbq)) || ((k==hbp)&&(X[k]==1)&&(hbp!=hbq)))

{ /* even number of 1s */

/* here there are two possibilities, both having 1s or no 1s at all */

/* both ones */

if((k != hbq) && (k <= hbp))

{

P[k] = 1;

Q[k] = 1;

if(!process(k+1, X, m, ones, 2, hbp, hbq))

return 0;

else if(sign)

return 1;

}

/* No ones */

if(k == hbp)

Q[k] = 0;

else if((k != hbp) && (k != hbq))

{

P[k] = 0;

Q[k] = 0;

if(!process(k+1, X, m, ones, 0, hbp, hbq))

return 0;

else if(sign)

return 1;

}

else if((((X[k]%2)!=0) && (k!=hbp) && (k!=hbq)) || ((k==hbp) && (X[k]==0)))

{ /* odd number of 1s */

/* here there are two possibilities, both having 1s or no 1s at all */

/* give it to P */

if(k == hbp)

if(!process(k+1, X, m, ones, 0, hbp, hbq))

return 0;

else if(sign)

return 1;

if(k < hbp)

{

P[k] = 1;

Q[k] = 0;

if(!process(k+1, X, m, ones, 1, hbp, hbq))

{

P[k] = 0;

return 0;

}

else if(sign)

return 1;

}

/* give it to Q */

if(k > hbp)

Q[k] = 1;

else if(k == hbp)

Q[k] = 0;

else

{

P[k] = 0;

Q[k] = 1;

}

if(!process(k+1, X, m, ones, 1, hbp, hbq))

{

Q[k] = 0;

return 0;

}

else if(sign)

return 1;

Q[k] = 0;

}

void mainprogram(void)

{

int i, j, k, flag = 0;

char ch;

clrscr();

{

sign = 0;

if(input())

{

initialize();

N[0] = 0;

ones--;

count = 0;

k = m;

for(i = 1; i <= k/2; i++)

{

j = k-i-1;

process(1, N, m, ones, 0, i, j);

if(sign)

break;

P[i] = 0;

Q[j] = 0;

}

if(!sign)

{

for(i = 1; i <= k/2; i++)

{

j = k-i;

process(1, N, m, ones, 0, i, j);

if(sign)

break;

P[i] = 0;

Q[j] = 0;

}

if(!sign)

printf("\n This number cannot be factorized.");

}

printf("\n Press q to back to main menu or any other key to continue: ");

fflush(0);

ch = getchar();

} while(ch!= 'q');

}

//---------function to show the help file----------------

void help(void)

{

FILE *fp;

char ch;

int l = 0;

clrscr();

if ((fp=fopen("\\help.txt","r"))==NULL)

{

printf("\n\tError reading help file.");

getch();

return;

}

printf("\n\n\n\t\t\tWELCOME TO HELP.\n\n\t\tHELP:-\n\n");

while(!feof(fp))

{

ch=getc(fp);

putchar(ch);

l++;

if(l>479)

{

l=0;

fflush(0);

getch();

}

fflush(stdin);

getch();

fclose(fp);

}

//----------graphics programming for the intoduction---------

void front(void)

{

int midx, midy, i, j, k, l = 0, count = 0, y = 0;

int gdriver=DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode,"\\tc\\bgi");

errorcode = graphresult();

if(errorcode != grOk)

{

printf("Graphics Error:%s\n",grapherrormsg(errorcode));

printf("Press any key to halt.");

getch();

exit(1);

}

setcolor(15);

settextstyle(1,0,4);

outtextxy(20,60,"INPLEMENTATION OF A NEW");

outtextxy(40,92," ALGORITHEM OF FACTORIZATION");

line(98,140,550,140);

line(150, 145, 580, 145);

setcolor(9);

settextstyle(13,0,3);

outtextxy(410,150,"PROJECT: CRYPTOGRAPHY");

outtextxy(370,170,"Supervized by: Mr. ENAMUL KARIM");

outtextxy(370,190,"Assisted by: MONIRUL ISLAM SHARIF");

setcolor(4);

midx=getmaxx()/2;

midy=getmaxy()/2;

setcolor(8);

ellipse(midx+midx/3,midy+midy/3+60,0,360,50,10);

setfillstyle(1,8);

floodfill(midx+midx/3,midy+midy/3+60,8);

setcolor(4);

circle(midx+midx/3,midy+midy/3,50);

setfillstyle(1,4);

floodfill(midx+midx/3,midy+midy/3+1,4);

rectangle(midx+midx/3-50,midy+midy/3-10,midx+35,midy+midy/3);

lineto(midx+10,midy+midy/3-4);

lineto(midx-10,midy+midy/3);

lineto(midx-30,midy+midy/3+10);

lineto(midx-50,midy+midy/3+30);

lineto(midx-70,midy+midy/3+35);

lineto(midx-90,midy+midy/3+40);

lineto(midx-150,midy+midy/3+40);

floodfill(midx+midx/3-51,midy+midy/3-9,4);

char s1[80] = " This program is submitted by Jolly, Mithu, Sami & Shahid.... ";

char s2[80] = " This program is submitted by Jolly, Mithu, Sami & Shahid.... ";

for(i=80;i>=1;--i)

{

for(j=0;j<80;j++)

{

if((i+j) <= 80)

gotoxy(i+j,25);

printf("%c",s1[j]);

if(i+j==80)

break;

}

if(i == 1)

{

i = 2;

l++;

for(k=0;k<80;k++)

s1[k] = s1[k+1];

for(k=1;k<l;++k)

s1[80-k] = s2[l-k];

}

if(l == 80)

l = 0;

settextstyle(7, 0, 2);

if(y>95)

outtextxy(395,425,"Openning menu......");

y++;

if(y>120)

{

setcolor(4);

circle(midx+midx/3+2,midy+midy/3+2,53);

setfillstyle(1,12);

floodfill(midx+midx/3+10,midy+midy/3+52,4);

circle(midx-150,midy+midy/3+40,3);

setcolor(14);

circle(midx-149,midy+midy/3+40,2);

setfillstyle(1,14);

floodfill(midx-149,midy+midy/3+40,14);

switch(count)

{

case 0:

for(i=0;i<60;i++)

putpixel(midx-150+i,midy+midy/3+40,getpixel(midx-149,midy+midy/3+40));

count++;

break;

case 1:

for(i=0;i<30;i++)

putpixel(midx-90+i,midy+midy/3+40-i/3,getpixel(midx-149,midy+midy/3+40));

count++;

break;

case 2:

for(i=0;i<20;i++)

putpixel(midx-70+i,midy+midy/3+35-i/3,getpixel(midx-149,midy+midy/3+40));

count++;

break;

case 3:

for(i=0;i<20;i++)

putpixel(midx-50+i,midy+midy/3+30-i,getpixel(midx-149,midy+midy/3+40));

count++;

break;

case 4:

for(i=0;i<20;i++)

putpixel(midx-30+i,midy+midy/3+10-i/2,getpixel(midx-149,midy+midy/3+40));

count++;

break;

case 5:

for(i=0;i<60;i++)

putpixel(midx-12+i,midy+midy/3-1,getpixel(midx-149,midy+midy/3+40));

count++;

break;

default:

for(k=450;k>0;k--)

circle(midx+midx/3,midy+midy/3,450-k);

return ;

}

if(kbhit())

{

skip = 1;

return;

}

delay(100);

}

closegraph();

getch();

}

//---------function to check input in menu-------------

int check(void)

{

union REGS in, out;

in.h.ah = 0;

int86(0x16, &in, &out);

return out.x.ax;

}

//----------function to draw cursor in the menu--------------

void drawrec(int del, int kept)

{

int y[] = {145, 178, 211, 243};

setcolor(0);

rectangle(153, y[del], 472,y[del]+33);

setcolor(BLUE);

rectangle(153, y[kept], 472, y[kept]+33);

}

//---------graphics programming for the menu-----------------

int menu(void)

{

int ch;

int gdriver = DETECT, gmode, i, j, k, l, key;

int static style = 0, khit = 0;

initgraph(&gdriver, &gmode,"\\tc\\bgi");

setbkcolor(0);

setcolor(13);

k = getmaxx();

l = getmaxy();

settextstyle(1,0,4);

if(!style)

{

for(i = 0; i <= 105; i++)

{

setcolor(10);

outtextxy(i,100,"INDEX :");

delay(3);

if(i != 105)

{

setcolor(0);

outtextxy(i,100,"INDEX :");

}

settextstyle(2,0,6);

for(i = k; i >= 155; i--)

{

setcolor(10);

outtextxy(i,152,"* MAIN");

delay(1);

if(i != 155)

{

setcolor(0);

outtextxy(i,152,"* MAIN");

}

for(i = k; i >= 222; i--)

{

setcolor(10);

outtextxy(i,152,"PROGRAM");

delay(2);

if(i != 222)

{

setcolor(0);

outtextxy(i,152,"PROGRAM");

}

for(i = 0; i <= 381; i++)

{

setcolor(10);

outtextxy(i,185,"BOUNDINGS");

delay(1);

if(i != 381)

{

setcolor(0);

outtextxy(i,185,"BOUNDINGS");

}

for(i = 0; i <= 305; i++)

{

setcolor(10);

outtextxy(i,185,"WITHOUT");

delay(2);

if(i != 305)

{

setcolor(0);

outtextxy(i,185,"WITHOUT");

}

for(i = 0; i <= 226; i++)

{

setcolor(10);

outtextxy(i,185,"PROGRAM");

delay(2);

if(i != 226)

{

setcolor(0);

outtextxy(i,185,"PROGRAM");

}

for(i = 0; i <= 155; i++)

{

setcolor(10);

outtextxy(i,185,"* MAIN");

delay(2);

if(i != 155)

{

setcolor(0);

outtextxy(i,185,"* MAIN");

}

for(i = k; i >= 155; i--)

{

setcolor(10);

outtextxy(i,215,"* HELP");

delay(2);

if(i != 155)

{

setcolor(0);

outtextxy(i,215,"* HELP");

}

for(i = 0; i <= 155; i++)

{

setcolor(10);

outtextxy(i,245,"* EXIT");

delay(2);

if(i != 155)

{

setcolor(0);

outtextxy(i,245,"* EXIT");

}

}}

if(style)

{

setcolor(10);

outtextxy(105,100,"INDEX :");

settextstyle(2,0,6);

outtextxy(155,152,"* MAIN PROGRAM");

outtextxy(155,185,"* MAIN PROGRAM WITHOUT BOUNDINGS");

outtextxy(155,215,"* HELP");

outtextxy(155,245,"* EXIT");

}

style = 1;

setcolor(BLUE);

rectangle(153, 145, 472,178);

if(!khit && skip)

l = check();

khit = 1;

one:

key = check();

if(key == 7181)

{

ch = 1;

closegraph();

return ch;

}

else if(key == 20480)

{

drawrec(0, 1);

three:

key = check();

if(key == 7181)

{

ch = 2;

closegraph();

return ch;

}

else if(key == 20480)

{

drawrec(1, 2);

two:

key = check();

if(key == 7181)

{

ch = 3;

closegraph();

return ch;

}

else if(key == 20480)

{

drawrec(2, 3);

four:

key = check();

if(key == 7181)

{

ch = 4;

closegraph();

return ch;

}

else if(key == 20480)

{

drawrec(3, 0);

goto one;

}

else if(key == 18432)

{

drawrec(3, 2);

goto two;

}

else if(key == 18432)

{

drawrec(2,1);

goto three;

}

else if(key == 18432)

{

drawrec(1, 0);

goto one;

}

else if(key == 18432)

{

drawrec(0,3);

goto four;

}

closegraph();

}

//-------graphics programming for the end show-----------

void end(void)

{

int i,counter = 0, y;

int gdriver=DETECT, gmode;

initgraph(&gdriver, &gmode,"\\tc\\bgi");

setbkcolor(BLACK);

setcolor(8);

for(i=0;counter<2;i++)

{

if(i == 16)

{

i = 0;

counter++;

}

settextstyle(1,0,4);

if(i <= 9)

{

setcolor(i);

outtextxy(10,200," THANK YOU FOR USING THIS PROGRAM.");

}

if(i > 9)

{

setcolor(i);

outtextxy(180,250,"* * * THE END * * *");

}

if(kbhit())

break;

delay(200);

}

closegraph();

}

/* All Quiet on The Western Front */

back to contents

9. EVALUATION OF RESULTS:

The evaluation of the result is presented in a tabular form below:

Inputs	Outputs (In Binary Mode)	The Primes	In the main program-m count	In the second case counts are
	(LSB) . . . ��(MSB)
66,98,261	10110110011001101000000 10010010000000000000000	91757 73	7652	10230
4,60,12,073	10111111100000000000000000 10111000100001101000000000	509 90397	16240	3577
4,97,49,569	10110100010000000000000000 10100111001110101000000000	557 89317	20903	28417
6,70,38,773	10111000000110101000000000 10011111010000000000000000	88093 761	25310	32753
7,02,95,047	110101001100000000000000000 101010010100101010000000000	811 86677	11904	5706
8,33,50,801	100010111100000000000000000 100000101011001010000000000	977 85313	37770	7801
8,68,56,503	110111111100000000000000000 101011110011001010000000000	1019 85237	10801	5991
20,75,32,483	1110010100110010100000000000 1010000110010000000000000000	85159 2437	14959	64136
25,00,88,327	1101111011010000000000000000 1010011000110010100000000000	2939 85093	22417	65861
25,67,62,931	1101001111010000000000000000 1001110000110010100000000000	3019 85049	30480	68387
37,37,84,573	10110100100010000000000000000 10001000001100101000000000000	4397 85009	54790	95434
29,81,00,617	10011110000101110000000000000 10001001110010000000000000000	59513 5009	57163	39520
33,39,55,233	11001010000001110000000000000000 10010100110001110000000000000000	57427 58153	122675	173401
2,72,25,43,939	11111110111000110000000000000000 10111100000010110000000000000000	53309 51071	2076	147268
14,50,957	101110000000000000000 100011101100001100000	29 50033	3158	274
36,29,40,601	11010110010100100000000000000 11010110010100100000000000000	19051 19051	29552	121232
12,31,13,891	110010010101100000000000000 100011010110001000000000000	6803 18097	25869	61298
25,77,469	1011100100000000000000 1000010000000010000000	157 16417	4029	6668
13,86,27,823	1100010011011100000000000000 1010001111000100000000000000	15139 9157	22452	38645
1,09,703	11010000000000000 10101111011001000	11 9973	643	1166

Figure: Comparison between the normal program (#1) and the program with bounding condition (#2).

back to contents

10. DISCUSSION:

◈ Here in these programs recursion is used as the backtracking tool. As for recursive function calls the stack is used to hold the previous stage condition. So in case of a fairly large number the program time increases and there is a possibility of stack overflow.

◈ The program with bounding works faster whenever the difference of the resulting prime numbers are good and the program with bounding works faster whenever the difference of the resulting two primes are very low.

back to contents

11. CONCLUSION:

Much study and observation is needed to improve the algorithm of finding unsafe keys in RSA implementation. Keys which have the pattern-type discussed here are proofed unsafe. If the work is continued then it can be proofed that a several pattern-typed keys are unsafe in RSA implementation, which apparently tighten the security of RSA cryptosystem.

back to contents

12. ACKNOWLEDGEMENTS:

Our honored thanks go to the project teacher for his very kind and time consuming co-operation�

MR. ENAMUL KARIM,

Faculty member, Dept. of Computer Science, Dhaka University.

Thanks also go to the course teacher and lab teachers-

MR. ABDUN NASER MAHMOOD & MR. S. M. TAREQ,

Faculty member, Dept. of Computer Science, Dhaka University.

For the program (without bounding function) thanks to-

MONIRUL ISLAM SHARIF,

M. SC. Student, Dept. of Computer Science, Dhaka University.

back to contents

13. REFERENCES:

1. Riesel H., Prime Numbers and Computer Methods for factorization, Birkh�user, Boston, 1994.

2. Tanenbaum A. S., Computer Networks.

3. Karim M. E. and Hasan M. S., A Backtracking Approach to Factorization, AI and Algorithm Research Lab, Department of Computer Science, University of Dhaka.

4. M. E. Karim, M. A. Mottalib. A New Approach to Computer Aided Factorization, Abstract of the 10^th Annual Conference of Bangladesh Mathematical Society, 1995

5. M. E. Karim, M. A. Mottalib. A New Approach to Integer Factorization, Proceedings of National Conference on Computer and Information Systems, Dhaka, 1997

6. Flannery S., Cryptography: An investigation of a new algorithm vs. the RSA, collected from http:\\ cryptome.org.

back to contents

M	E	G	A	B	U	C	K
7	4	5	1	2	8	3	6
p	l	e	a	s	e	t	r
a	n	s	f	e	r	o	n
e	m	i	l	l	i	o	n
d	o	l	l	a	r	s	t
o	m	y	s	w	i	s	s
b	a	n	k	a	c	c	o
u	n	t	s	i	x	t	w
o	t	w	o	a	b	c	d

M	E	G	A	B	U	C	K
7	4	5	1	2	8	3	6
p	l	e	a	s	e	t	r
a	n	s	f	e	r	o	n
e	m	i	l	l	i	o	n
d	o	l	l	a	r	s	t
o	m	y	s	w	i	s	s
b	a	n	k	a	c	c	o
u	n	t	s	i	x	t	w
o	t	w	o	a	b	c	d

M	E	G	A	B	U	C	K
7	4	5	1	2	8	3	6
p	l	e	a	s	e	t	r
a	n	s	f	e	r	o	n
e	m	i	l	l	i	o	n
d	o	l	l	a	r	s	t
o	m	y	s	w	i	s	s
b	a	n	k	a	c	c	o
u	n	t	s	i	x	t	w
o	t	w	o	a	b	c	d