Thank you for visiting our site! You landed on this page because you entered a search term similar to this: calculating greatest common factor, here's the result:
Stonehill College
Data Structures and Discrete Mathematics Learning Community
Professors Ralph Bravaco and Shai Simonson
Cryptography Laboratory
Introduction
In this lab, you will experiment with cryptographictechniquesthat are the foundation for today’s e-commerce and internetcommunication.In World War II the war behind the war was all about the Britishtryingto intercept and decode German transmissions. (Check herefor the contributions of the famous pioneer computer scientist, AlanTuringin this effort.)
A simple version of the codes used in World War II works likethis. The alphabet is shifted over by some number of letters, so that “a”mightbecome “f”, and “b” would be “g”, etc., wrapping all the wayaround. We could call that the f-shift. The substitutions for the f-shiftare shown below:
abcdefghijklmnopqrstuvwxyz
fghijklmnopqrstuvwxyzabcdeFor example, the word “shai” is encoded into “xmfn” using thef-shift. Note that the f-shift is nothing more than adding 5 to each letter’sasciivalue. You need to be careful to wrap around appropriately modulo26.
If that was all there was to encoding, then a code breaker wouldonlyhave to try 25 possibilities to break the code. A codebreakersimplytries translating the message using each of the letter shifts until onetranslation looks like a real message.
The Germans were more clever in creating their encodings. Thetrick they used (more or less) was to have each subsequent letter use adifferent shift. After a while these shifts would cycle. Thesequence of shifts was represented by a code word consisting of lettershifts. For example, if the codeword was “remarkable”, then thefirstletter of the message would shift by 17, the second letter by 4, …, the7th letter by 0 etc. The 11th letter would shift by 17 again likethe first and the cycle would start to repeat.
For example, the first few characters of the sentence “We meet inNewYork for a rendezvous” would be encoded as “Ni ye…”. Note thatspacesbetween words were not actually transmitted or encoded.
Checkpoint: See if you can encode the rest of thesentenceyourself by hand.
For a codeword like “remarkable” of length ten, there are now 2610different possible encodings. The longer the sequence of thecycle,the more possibilities there are.
Breaking the Code
Once one knows the length of the cycle, there are a numberof techniques for breaking the code without having to try all thepossibilities.One idea is to divide the letters of the encoded message up into 10groups,one for each shift in the cycle. The 1st, 11th, 21st etc make thefirst group. The 2nd, 22nd, 32nd etc. make the secondgroup. And so on. The letters in each group are encoded using the sameshift.We try to decode the letters a group at a time. For eachgroup,we try all 26 possible shifts, but since the letters in each group arescattered throughout the message, we are unlikely to learn anything bydoing this. The chance of something looking familiar will be verysmall.
There is a way to learn something about the messagenevertheless. Every language has a characteristic statistical frequency for eachletter. For example, in English the letter “e” is the most common. For agiven group, we compare the frequencies of the letters in each of the26decodings to the expected frequencies. Matching the two sets offrequencieshelps identify the shift or at least narrows down the number ofpossibilitiesfrom 26 to just a few.
The Germans actually used a more complex version of cycles ofshiftsthat required an even more sophisticated computer-aided decodingeffort. The end of the story was that the British were successful in theireffortsand the Allies prevailed.
Program 1. A cycle of shifts is described by acodeword like REMARKABLE, where each letter represents a shift, A is 0,B is 1, … and Z is 25. Write a program that takes a text and acodeword,and produces the encrypted text. You will need to use the % (mod)operator to make sure you wrap around appropriately. Youmightwant to keep the codeword in circular linked list.
Program 2. Modify your program so that it candecode as easily as it encodes. All you need to do is add an option todecode, and then do subtraction rather than addition.Make a note of how symmetric this is! This was the hallmarkofcryptography since ancient times, until the last twenty years. Ifyou knew how to encode something, then you knew how to decode it. You might be thinking “well duh!!”
Determining the Cycle Length
An ingenious method to determine the cycle length was discovered whose paper is described in his seminal historyof cryptography as "the mostimportantsingle publication in cryptology." Friedman defines theindexof coincidence, a statistical measure of text, that for normal Englishis about 6.6%, but for a random collection of letters is only about3.8%.To determine the index of coincidence of a particular piece oftext,take the text, rotate it by some random number of places, and write therotated text underneath the original text. For example, thesentencebelow is rotated by 58 characters and the rotated version appearsbeneathit.
alanturingbreakscodeslikenobodysbusinessbuthispersonallifesadlybecameeverybodysbusiness
dysbusinessbuthispersonallifesadlybecameeverybodysbusinessalanturingbreakscodeslikenoboThe index of coincidence is the number of places in which the sameletteroccurs in both strings of text. In this example, there are 6coincidencesfor 87 characters of text, a rate similar to the 6.6% of normal Englishtext. An important point to notice is that when a text isencryptedby shifting every letter by the same value, the index of coincidenceremainsthe same.
Given an encryption of the same text with a codeword wewouldexpect to see an index of coincidence more like the 3.8% of randomletters,unless we happen to have rotated by a multiple of the cyclelength. In the case where the rotation is a multiple of the cycle length, thelettersthat are lined up underneath each other are encoded using the sameshift,and the usual English index of coincidence would be expected, becausetheindex of coincidence is invariant under a single letter cipher. Hencethe way to determine the cycle length is to rotate the encrypted textby1, 2, 3 etc. symbols, until we see an index of coincidence that looksmorelike 6.6% than 3.8%.
Program 3. Write a program that calculates the cyclelengthof an encoding by searching for an index of coincidence close to6.6%. You can use your earlier programs to create test data.
Public Key Cryptography - A Revolution in Cryptography
Cryptographic methds do not have to be symmetrical! Todaya new kind of encoding is used which is called Public Key, one-way, orsometimes trapdoor cryptography. In this new method, the wholeworldis able to encode information, but unless someone has more information,then they still cannot decode a message.This new method is what allows e-commerce to flourish without fearofa security breach. Here’s how this trapdoor technology isused. Say I want to send my credit card to Amazon.com to buy a book, I encodemy number with a publicly published method that anyone else could use,but only Amazon.com can decode it!
What if I don’t trust that I am actually talking toAmazon.com? That is, I suspect that a thief posing as Amazon, sent me a fakeencodingalgorithm, and then they will decode it and get my number! Inthatcase, we do the process in reverse. I ask Amazon to send me amessageencoded with their secret encoding that anyone can decode with theirpublicalgorithm. If I decode the message and it states, “Hi I amAmazon.com”,I know it had to come from them, because nobody else would have knownhowto encode it correctly. This is called authentication and isdescribedin nice detail by VeriSign, the largest digital signature provider, at
The Mathematics Behind Public Key Cryptography
Ironically, this new extremely practical technology isbasedon one of the oldest branches of pure mathematics, famous for itsbeautyand scarcity of practical applications: number theory.The details of public-key cryptography are based on the RSAalgorithm,by Rivest, Shamir, and Adelman. We will review the mathematicsherebriefly here and end with a few experiments and programs.
Euclid’s Algorithm and Greatest Common Divisors
The greatest common divisor of two integers is the largestinteger that divides both evenly. For example, the greatestcommondivisor (gcd) of 24 and 15 is 3. One way to calculate the gcd of twonumbers,a and b, is simply try all numbers starting from the smaller of the twodown to one. The first of these numbers that divides both a and bevenly, is the greatest common divisor.
Program 4. Write a program to find thegreatestcommon divisor this way.Program 5. Write a program to find the greatestcommon divisor by listing the prime factors for each number,and taking the intersection of the two lists. A nice way to dothis is to storethe prime factors sorted in twoarrays,and then use an algorithm that resembles merging. For example, ifthe two numbers are 24 and 40, then the prime factors of 24 are: 2, 2,2, 3, and the prime factors of 40 are: 2, 2, 2, 5. Theintersection of these two lists is 2, 2, 2, so the gcd is 2x2x2 = 8.
Although the methods used in both program 4 and 5 are intuitiveand seem natural,neitheris the best way to find greatest common divisors. It will beimportantto us later to be able to find the greatest common divisor efficientlywithout factoring the given numbers.
Euclid (300 B.C.E.) invented a method to compute greatest commondivisorsthat bears his name to this day. In Euclid’s algorithm, we userecursion. He proved that assuming a>b, then the gcd(a,b) = gcd(b, a modb). An example is shown below.
| | |
| | |
| | |
| | |
| | |
| | |
| | |
When the smaller number, b, equals 0, then the answer isa. In this case, the gcd(123, 28) = 1.
Program 6. Write a recursive program toimplementEuclid’s algorithm. Write an iterative program to implementEuclid’salgorithm.Experiment. Test your three programs on a variety ofpairsof numbers, time them, and discuss the results. Note thattheoreticallyEuclid’s algorithm takes time proportional to the number of digits inthenumbers, while the other two algorithms take time proportional to thenumbersthemselves (an exponential explosion in complexity).
Connection to Cryptography
It is not obvious that Euclid’s algorithm has a lot to dowithRSA public-key cryptography, but it does. You will need to bepatient.A theorem of Euclid that we will not prove here, states that ifthegcd(a,b) = m, then there are two integers x and y such that ax +by = m. These values x and y can be computed constructively usingEuclid’s algorithm. Here is an example using the numbers from theprevious example.
123 = 28(4) + 11The greatest common divisor was 1. Now we work our way backwards:
28 = 11(2) + 6
11 = 6(1) + 5
6 = 5(1) + 11 = 6 – 5(1)
1 = 6 – (11 – 6(1))(1) = 6(2) – 11(1)
1 = (28–11(2))(2) – 11(1) = 28(2) – 11(5)
1 = 28(2) – (123 – 28(4))(5) = 28(22) – 123(5)
Each step gives us the x and y for the pair of numbers onthatlevel, until finally we arrive back at the original pair of numbers 28and 123, where the x and y are 22 and –5 respectively. Study thisexample, and try to understand exactly what is going on. (You maynotice that the solutions for x and y are not unique. In class,wewill discuss more details and variations of this method. But forthe purposes of this lab, you won’t need to know anything more aboutit.)
Checkpoint: To make sure you get the ideaabove,compute by hand, the integers x and y, such that ax + by = gcd(a,b) foreach pair a, b below.
(99, 101) (10, 35) (7, 12) (36, 42)Although the next program is only three lines long, you willlikelyneed a hint trying to figure out how to relate the computation of thenextrow’s x,y values to the previous row’s.
Program 7. Write a recursive program tocalculatethe integers x and y, such that ax + by = gcd(a,b) for a given pair aandb. This program will be crucial for the RSA cryptographyalgorithm. Try your program out on the numbers 233987973 and 41111687.
Hints for program 7: If gcd(a,b) = a mod b, we are atthelast row, and we can return (x,y) = (1, -(a/b) ). Otherwise, wemustrecursively compute the function with the inputs (b, a mod b). Callthe outputs of this recursive call x' and y'. Then the originalfunctioncan return (x,y) = (y', x' - (a/b)y'). Try this on the exampleabovefor 28 and 123, and I will review the example in class if necessary.
Public Key Cryptography – A First Attempt
This section describes a method that is a simple version ofRSA, but has the drawback that the private key can be computed from thepublic key using program 6 that you wrote earlier. Study thissimpleversion first, because although it does not quite work because of thedrawbackmentioned, it will give you a chance to understand what is really goingon before tackling RSA proper.All the public key cryptographic methods encode one integer intoanother,so we assume that our messages are first converted to a sequence ofintegers. The exact method of conversion is not trivial but it won’t concern ushere.
To encode a number, we will need the public key. Thisconsistsof two integers, for example 5 and 17. The second integer must beprime, and the first must be relatively prime to the second integerminusone. In this case, 17 is prime, and 5 is relatively prime to16. Recall that two numbers are relatively prime if and only if theirgreatestcommon divisor is equal to one.
Encoding and Decoding Numbers – Public and Private Keys
Now to encode a number, say 6, using this key. All we do iscalculatethe remainder of 65 after dividing by 17. You cancheckthat this equals 7. To decode 7 back into 6, we need to have theprivate key. The private key also consist of two numbers, one ofwhich is really public, namely the prime 17, and one of which is reallyprivate namely 13. Then we calculate the remainder of 713after dividing by 17, and we get 6.Where does the 13 come from? Why does this work?
Thirteen is the solution to the equation 5x = 1 mod 16.
What happened here is that we computed 65(13) mod 17 = 713mod 17 = 6 mod 17. Since 5(13) = 1 mod 16, we can write5(13)= 16(4) + 1. This means that that 616(4) + 1 = 6 mod17,and equivalently 616(4) = 1 mod 17. It turns out thatthis must happen as long as 5(13) = 1 mod 16, and 5 has no commonfactorswith 16. There is a theorem to justify this.
Fermat’s Little Theorem
Pierrede Fermat, was an amateur but great mathematician of the early 17thcentury. Fermat’s Little Theorem, not to be confused with hismorefamous Last Theorem states:If p is a prime, and is not divisible by p, then p evenly divides ap-1- 1. For example, if p equals 17, and a equals 6, then 17 evenlydivides 616 – 1, or 616 = 1 mod 17. Theproofis left for the discrete math class. It is elegant butirrelevantfor this lab. It is the result that we need. If 616= 1 mod 17, then certainly 616(4) = 1 mod 17, and ourencodingand decoding will work.
Computing Inverses
It doesn’t matter if you understand all the mathematics here, but youdoneed to understand how to calculate this number 13. Recall thatthirteenwas the solution to the equation, 5x = 1 mod 16. That means wemustfind two numbers x and y such that 5x – 16y = 1. Soundfamiliar? It is just Euclid’s algorithm!The numbers 5 and 13 are called inverses of each other mod16. That means they multiply together to equal one. The computationofan inverse is just what you did in program 6.
Now What? If a person wanted to calculate the private keyfromthe public key, they could do it by just using your program 6 andcalculatingthe inverse of the private key mod 16. What’s wrong is that it ispossible to calculate inverses quickly and efficiently. You wrote aprogramto do it yourself! So if someone publishes a public key (5, 17)youcould have your program compute the private key (13, 17). That isnot good enough. We want the decoding to be harder than theencoding. We do not want anyone to be able to find 13 so easily. Only thepersonwho holds this private key can decode.
A Second Attempt at Public Key Cryptography
The first attempt described above is based on work byDiffieand Hellman in 1976 (see andwas known before the contributions of Rivest, Shamir, and Ademan (RSA)in 1977. The RSA contribution is described next.
Now we start with two prime numbers, p and q, say 2 and 17, and computetheir product pq = 34. We calculate (p-1)(q-1) = 16, and wechoosea value that has no common factors with 16, say 5. The public keybecomes the pair of numbers 34 and 5.Encoding and Decoding
The encoding and decoding is done just like before. For example,to encode 6, we compute 65 mod 34 = 24 and to decode 24 wecompute2413 mod 34 = 6. As before, thirteen is the solutiontothe equation 5x = 1 mod 16.The difference between this and our first attempt is thatpreviously,16 was simply one less than the public prime, so that the equation, 5x= 1 mod 16, was easily constructed (and solved by program 6). Butnow the only way to calculate 16, is to factor the number 34 into 2 and17 and compute (2-1)(17-1). The factoring part is hard! Nobodyknows how to factor numbers quickly. The best method isproportionalto the given numbers. Contrast this with the calculation of theinversethat is exponentially faster, proportional only to the number of digitsin the given numbers.
Of course, anybody can factor 34, but in practice the two primesthatare chosen are on the order of 100 digits each. This makes allcurrentlyknown factoring algorithms take centuries. If you come up with anefficient algorithm (like the one for inverses) that can factornumbers,you will be famous!
Checkpoint
a. Create your own public and private codes for doing RSAencrypting. Make sure they satisfy all the appropriate constraints.
b. Assuming that each character in a message is represented by itsASCII value, encode the message “Too much work!”.
Program 8. Write a program to encode numbersusingRSA given the public key. Make sure to use the fast modularexponentiation algorithm we discussed in class. That will allowyou to deal with very large numbers efficiently. Raising x to the yth power can be done in timeproportional to log y.Program 9. Write a program that factors the publicprime,into p and q, computes (p-1)(q-1), computes the inverse to find theprivatekey, and decodes a message. Use your program to solve thefollowingproblem.
Puzzle. Cracking the UFO Message.
A public code is found etched on a rock on Mars: (7, 1147). The message {128, 1040, 129, 1144, 788, 735, 570, 875} is received fromouter space on one of the billion machines running the ExtraterrestrialLife Detector Screen Saver distributed among the world’s PC’s. Assumingthat this message was encrypted with the public code found on Mars,crackthe code and decode the numbers. (Note that this problem usessmallprimes, hence giving your program a fighting chance to succeed beforeweare all dead.)
Note that to use RSA on integersthat are large which is the whole idea, you will need to use a bigintclass, in order to avoid overflow. Here is a stack class toinclude inbigint stack andhere is another.
Cryptographic Decoding Challenges for Practice and Review
Challenge 1.
A code word less than six letters long gives an encoding of a wellknown cerebral song:
BQHIERPVBZXOPORHASACNFLQHBYSKFBBZKBHAHASYZHKXFLQHBLIEHBBZKBHAHASKOBB
PWMVMVXHACNUAHLWWPXHAWGYBBBQHIERUSTBHHASKZBBVCEBBTBCGZRVTRTPKOBBWhat is the original text?
Challenge 2.
A code word less than six letters long gives an encoding of a WoodyAllen math joke:
BOQWMNWOOQSSFHQKASRLAGOWRAADWRKAONCIOHKJKCYHVYWHLLCWhat is the text?
Challenge 3.
RSA encoding of nine ascii values, using public key (10555, 21971),givesthe name of a hunter:
16912 19531 20676 16912 6613 2348 17835 15770 15770What is the original text?
Challenge 4.
RSA encoding using public key (5555551, 118513313) gives:
80217189 107242213 96490860 79543571 25953566What are the original numbers?
Challenge 5.
Factor any of the RSA challenge numbers atRSA-Security
Read about a group of people called Bovine RC5 who successfullycrack RSA keys.