ArtsAutosBooksBusinessEducationEntertainmentFamilyFashionFoodGamesGenderHealthHolidaysHomeHubPagesPersonal FinancePetsPoliticsReligionSportsTechnologyTravel

Modular Mathematics: Or How Computers Encrypt Messages

Updated on July 3, 2014
Source

Have you ever wondered how cryptation of messages between computers work? It certainly is different than in the old age, when two people would agree on a code in secret, and then send messages with it. Two computers have no way of meeting and agreeing on a code over the Internet without risking that communication being snapped up by others. You would need to have a means of cryptation before you could agree on the cryptation you would use, and that obviously does not work. I am not an expert on technology, but I do study mathematics, and since that is the field which came up with the solution, I am here going to do a simple explanation of the mathematics behind modern encryption.

Theory: Modular Mathematics

First, a little bit of theory. Computer encryption rests on number theory, and more specifically, modular math. What is modular math? Consider a clock. It only has numbers from 1 to 12. Addition of two numbers works normally, but if you do 11+3, you get 2. To generalize, when you get above or under the thresholds of 1 or 12, you either add or substract 12 to end up on inside the interval 1-12. This is modular math, the only difference being that we there use 0 instead of 12, so 11+1=0, and the interval is 0-11. This is called mathematics modulo 12, but we can do this for any natural number n. In modulo 3 we have that 1+1=2, 2+1=0 and 2×2=1, for example.

More Theory: Euler Totient Function

One other part from number theory needs to be understood, although I shall not give the proofs for any of this. We have something called the Euler totient function, denoted here by φ(n), n being any natural number. This function describes how many numbers lower than n are relatively prime to n. To numbers are relatively prime if there is no number larger than 1 that divides them both. 6 and 8 are not relatively prime, as both can be divided by 2. 7 and 9, however, are, as you can test by trying any number lower than 7.

φ(n) counts the number of relatively prime numbers smaller than itself any number has. φ(8)=4, since 1,3,5 and 7 are relatively prime, an 2,4 and 6 are not. φ(14)=6, as 1,3,5,9,11 and 13 are relatively prime, and 2,4,6,7,8,10 and 12 are not. Now, without proof, I shall state a formula of immense importance to encryption, Euler's theorem: if a and n are relatively prime, then aφ(n)=1 modulo n. So a to the power of φ(n) equals 1 modulo n. From this it follows that aφ(n)+1=a modulo n, which we get by multiplying by a on both sides.

As a final note, φ(n) can be easily found if you know which prime numbers make up n. This will also be important.

Source

How it is Done

Now we have the tools needed. What we want is a way of encrypting so that knowing how to decrypt does not reveal how to decrypt, to get the original message back. Look at the classic codes, where you would for example replace A with G, B with O and so on. If you knew how to encrypt this, you would know how to reverse the process. But what about something more like a padlock, one of those you can lock without the key? You could send the lock without to your friend, he could lock whatever needed locking, and send it to you, where you use your key. If someone steals the lock, they can only lock things, not open your mail.

And this is modern cryptation. First, you take two prime numbers, large and unknown to anyone else. Multiply them, this is your number n. Find your φ(n), and add 1. Now find two numbers which when multiplied becomes φ(n)+1. This is rather simple thanks to your knowledge of the prime numbers used to make n and the fact that these numbers, e and d, are not prime numbers, but it requires some more theory. One of these numbers, we may call it e, and the number n, becomes your public key, available to anyone. They can encrypt a message with it by turning the message into a number a, and take that to the power of e modulo n. ae modulo n. This number is sent to you.

As you may know (ab)c=ab×c. So given the number ae, simply take this to the power of d modulo n, d being a number only known to you, and you have ab×e modulo n=aφ(n)+1 modulo n=a modulo n, our original message. Note that this only works if a is smaller than our original prime numbers, but this is easily done by splitting the message up in parts if it gets too big. Now you have your message, and no one who does not know d can decrypt it. This is how cryptation works, mathematically.


The trick to this method is the number n. If you know which two prime numbers n is made of, it is easy to figure out n, and to figure out what e and d is. But to have n and find the two prime numbers is a much more difficult task. There seems to be no easy way to do this, except going through the list of all prime numbers, trying each one.

An Example

And finally, an example, but with much lower numbers than computers use. Often the size of only one prime number which composes n can be of the magnitude of 10100, which ensures that it is almost impossible to guess it just by going through a list of prime numbers. But just to demonstrate, here is an example done with numbers small enough for a calculator.


Let our prime numbers be 3 and 11. n=33, and φ(n) we can calculate to be 20. This can be done by using the prime numbers. So we want two numbers which when multiplied becomes 21. These numbers being so small, we can just inspect the number and find that 3 and 7 fits the bill.

So our public key, the information we give to other computers, is e=7, and n=33. Say someone wants to send the message 5(remember, it must relatively prime from 33). 57 modulo 33= 14. So you get sent 14. Next: 143 modulo 33= 5, just like it should be. And that is how it is done.

Comments

    0 of 8192 characters used
    Post Comment

    • RonElFran profile image

      Ronald E Franklin 4 years ago from Mechanicsburg, PA

      I never before understood how public key encryption could be possible - how it is possible to provide a known encryption key that could not be used to decrypt messages encrypted with that key. This helps me see how it works. Thanks for throwing light on an interesting subject.

    working

    This website uses cookies

    As a user in the EEA, your approval is needed on a few things. To provide a better website experience, hubpages.com uses cookies (and other similar technologies) and may collect, process, and share personal data. Please choose which areas of our service you consent to our doing so.

    For more information on managing or withdrawing consents and how we handle data, visit our Privacy Policy at: "https://hubpages.com/privacy-policy#gdpr"

    Show Details
    Necessary
    HubPages Device IDThis is used to identify particular browsers or devices when the access the service, and is used for security reasons.
    LoginThis is necessary to sign in to the HubPages Service.
    Google RecaptchaThis is used to prevent bots and spam. (Privacy Policy)
    AkismetThis is used to detect comment spam. (Privacy Policy)
    HubPages Google AnalyticsThis is used to provide data on traffic to our website, all personally identifyable data is anonymized. (Privacy Policy)
    HubPages Traffic PixelThis is used to collect data on traffic to articles and other pages on our site. Unless you are signed in to a HubPages account, all personally identifiable information is anonymized.
    Amazon Web ServicesThis is a cloud services platform that we used to host our service. (Privacy Policy)
    CloudflareThis is a cloud CDN service that we use to efficiently deliver files required for our service to operate such as javascript, cascading style sheets, images, and videos. (Privacy Policy)
    Google Hosted LibrariesJavascript software libraries such as jQuery are loaded at endpoints on the googleapis.com or gstatic.com domains, for performance and efficiency reasons. (Privacy Policy)
    Features
    Google Custom SearchThis is feature allows you to search the site. (Privacy Policy)
    Google MapsSome articles have Google Maps embedded in them. (Privacy Policy)
    Google ChartsThis is used to display charts and graphs on articles and the author center. (Privacy Policy)
    Google AdSense Host APIThis service allows you to sign up for or associate a Google AdSense account with HubPages, so that you can earn money from ads on your articles. No data is shared unless you engage with this feature. (Privacy Policy)
    Google YouTubeSome articles have YouTube videos embedded in them. (Privacy Policy)
    VimeoSome articles have Vimeo videos embedded in them. (Privacy Policy)
    PaypalThis is used for a registered author who enrolls in the HubPages Earnings program and requests to be paid via PayPal. No data is shared with Paypal unless you engage with this feature. (Privacy Policy)
    Facebook LoginYou can use this to streamline signing up for, or signing in to your Hubpages account. No data is shared with Facebook unless you engage with this feature. (Privacy Policy)
    MavenThis supports the Maven widget and search functionality. (Privacy Policy)
    Marketing
    Google AdSenseThis is an ad network. (Privacy Policy)
    Google DoubleClickGoogle provides ad serving technology and runs an ad network. (Privacy Policy)
    Index ExchangeThis is an ad network. (Privacy Policy)
    SovrnThis is an ad network. (Privacy Policy)
    Facebook AdsThis is an ad network. (Privacy Policy)
    Amazon Unified Ad MarketplaceThis is an ad network. (Privacy Policy)
    AppNexusThis is an ad network. (Privacy Policy)
    OpenxThis is an ad network. (Privacy Policy)
    Rubicon ProjectThis is an ad network. (Privacy Policy)
    TripleLiftThis is an ad network. (Privacy Policy)
    Say MediaWe partner with Say Media to deliver ad campaigns on our sites. (Privacy Policy)
    Remarketing PixelsWe may use remarketing pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to advertise the HubPages Service to people that have visited our sites.
    Conversion Tracking PixelsWe may use conversion tracking pixels from advertising networks such as Google AdWords, Bing Ads, and Facebook in order to identify when an advertisement has successfully resulted in the desired action, such as signing up for the HubPages Service or publishing an article on the HubPages Service.
    Statistics
    Author Google AnalyticsThis is used to provide traffic data and reports to the authors of articles on the HubPages Service. (Privacy Policy)
    ComscoreComScore is a media measurement and analytics company providing marketing data and analytics to enterprises, media and advertising agencies, and publishers. Non-consent will result in ComScore only processing obfuscated personal data. (Privacy Policy)
    Amazon Tracking PixelSome articles display amazon products as part of the Amazon Affiliate program, this pixel provides traffic statistics for those products (Privacy Policy)