Thank you for visiting our site! You landed on this page because you entered a search term similar to this: great common divisor formula javascript.We have an extensive database of resources on great common divisor formula javascript. Below is one of them. If you need further help, please take a look at our software "Algebrator", a software program that can solve any algebra problem you enter!
RSA Demo Applet
The following Java Applet demonstrates the basics ofRSA Public Key cryptography. It was written a faculty member in the CIS Departmentat Baruch College, CUNY. You may contact Dr. Holowczak at:You may wish to read an overview of RSA Public Key Cryptography.
To operate the demo:
- Provide values for p andq (where p and q are prime numbers. Try p = 223 and q = 199) and click on the Calculate N button. This will calculatethe value of N (called the modulus). It will also provide values for E and D (the public and privateexponents) such that:
- E E is Relatively Prime to (p - 1) * (q - 1)
This means that E and (p - 1) * (q - 1) have no common factors except 1 - E * D - 1 is evenly divisible by (p -1) * (q - 1)
We call (E, N) the Public Key and (D, N) the Private Key.
To start with, you might want to just leave the values of p and q as they are. The reason is that if p and q aretoo small, then N will be smaller than the values we aretrying to encrypt or decrypt. When this happens, thesystem does not work properly.
Just as a check, it seems N should be greater than 40,000.This will allow all of the ASCII characters up to 128 to beencoded without problems.
- E E is Relatively Prime to (p - 1) * (q - 1)
- Next type a short message into the M field andclick on the Encrypt button. This will encryptyour message by combining two letters at a time intoa block. Each block will be encrypted usingthe RSA algorithm:
blockE mod NThe result will be the encrypted message shown inthe Ciphertext field.
- Clicking on the Decrypt button will then reverse the process by decrypting each of the encrypted values using the RSA algorithm:
blockD mod N
Your comments and suggestions are welcome: Richard Holowczak
Overview of RSA Public Key Cryptography
Cryptography can be used to encrypt (scramble) amessage for delivery over an insecure channel.We call this encrypted message ciphertext.Since the ciphertext is encrypted, anyone intercepting it would be unable to read it. On thereceiving end, the ciphertext is then decrypted toreveal the original message.A digital Key is a set of bits that are used toencrypt and decrypt messages. A form of cryptographycalled Public key cryptography uses two different keys:
- A Public Key which is used is used to encrypt messages.
- A Private Key is used to decrypt ciphertext and reveal the original message.
Public and Private keys are generated in pairs so that onlya specific pair of keys can perform the encryption anddecryption functions. Any keys other than the specific pairwill not work. A Public key is made known to everyone in theworld. The matching private key is kept a secret by itsowner.
In the following example, Alice would like to senda message to Bill. She uses Bill's Public Key (which everyoneknows) to encrypt the message. The ciphertext is then sentto Bill. Once he receives it, he can decrypt the ciphertextusing his Private key. Only Bill's Private key can be usedto decrypt.
![[Public Key CryptographyImage: publickey.gif]](publickey.gif)
RSA is a particular form of public key cryptography named after its inventors: Ronald Rivest, Adi Shamir, and Leonard Adleman in 1977. In RSA cryptography, a public and private key pair are generated using the following steps:
- Choose two large prime numbers p and q
Generally, p and q are over 100 digits long. - Compute the value of the modulus n as: n = p * q
- Choose a key E that is relatively prime to (p-1) * (q-1)
Choose a key D such that E*D = 1 mod (p-1) * (q-1)
In other words, E*D - 1 is evenly divisible by [ (p-1) * (q-1) ] - The Public Key is the combination of (E,n)
This is used to encrypt messages. - The Private Key is the combination of (D,n)
This is used to decrypt ciphertext and reveal the original message.
Given a Message M, to encrypt into ciphertext C, weuse the following formula:
C = ME mod n
Our public key is (E, n)
Given a Ciphertext C, to decrypt into plaintext message M we use the following formula:
M = CD mod n
Our private key is (D, n)
In practice, the message M is broken up into blocks (e.g., 64 bits at a time) and processed by the encryption algorithm.
The strength in RSA lies in the difficulty of factoring n. That is, guessing p and q given onlythe value of n. Currently this is a difficult problemin mathematics. A brute force approach, that is trying allpotential p and q would take many thousands ofyears (depending on the size of the original p and q).
As the number of digits in p and q grow large,factoring becomes more difficult.So we consider the Key Size as directly related to thestrength of the encryption.With n at 512 bits (154 digits), we consider this to be strong encryption. Total key size (E, n) or (D, n)would be 1024 bits.
Details of RSA cryptography and other cryptographytechniques can be found in the RSA web site:
In particular, the 216 page FAQ contains a significantnumber of definitions of concepts related to security, cryptography and Electronic Commerce.
How does this demo work?
Java to the Rescue
I had originally attempted to provide a demo using severalother tools such as MS Excel, JavaScript and others. However,I kept running into the problem that as the numbers got verylarge, these environments could not represent them accurately.I could have written something in C++ (which includes classesfor arbitrary sized integers), however, I wanted something thatwould be easily portable and accessible over the web.Fortunately, I came across a special feature of Java calledthe bigInteger class described here.
This demo was written in the Javaprogramming language. Specifically, it runs within a web browseras what is called a Java Applet. It was developed using the Java Development Kit version 1.1. The JDK 1.1 includes a specialclass called bigInteger that allows arbitrarily sizedintegers to be stored and operated upon. For example, the E, N and Dare all represented as type bigInteger in the applet.
Generating the Public and Private Keys
The first part of the demo provides text boxes where the user can supply the values of p and q. Ideally p and qshould be large prime numbers, however for the purposes of this demo,relatively small (less than 1000) values can be used. Presentlysimple checks are done on p and q to see if theyare indeed prime.
Once p and q have been specified, clicking on the Calculate N button will generate the modulus n as p * q and will also calculate (p-1) * (q-1)which is used for other calculations later on.
The value of E is then automatically suggested as a number that is relatively prime to (p-1) * (q-1). This is accomplished by looping a variable from 2 to N and checking to see if the greatestcommon divisor (GCD) of this variable and (p-1) * (q-1)is one. Typically, the variable reaches 5 as its choice forE. Fortunately, the bigInteger class includes a method calledgcd(bigInteger) that returns the GCD of two bigIntegers.
The value of D is then suggested by computing the mod-inverseof E. This gives a value for D such that E*D = 1 mod (p-1) * (q-1)
Once again, the bigInteger class comes to the rescue with a method calledmodInverse. This method is used to derive D given thevalue of E.
Encrypting a Message
At this point, we have now generated the necessary Public Key (E,n)and Private key (D,n). A message can be typed into the message field (labled M) and theEncrypt button can be clicked on.
Clicking on the Encrypt button causes the following steps to take place:
- Each letter in the message is represented as its ASCII code number. In ASCII, 'A' is coded as 65, 'B' is coded as 66 and so on.
to see a list of ASCII codes.
For this example, the message "Secret!" is coded as: 83 101 99 114 101 116 33 - Each ASCII code number is then represented in binary notation using 8 bits.
For this example, the binary codes become: 01010011 01100101 01100011 01110010 01100101 01110100 00100001 - Each pair of characters is then assembled into blocks. This is done by taking two 8 bit numbers and representing them side by side as one 16 bit number. In this example, there are 7 original characters that form 4 blocks:
0101001101100101 0110001101110010 0110010101110100 0000000000100001
Note that the last character is padded with zeros.
Real applications of RSA use blocks of up to 8 or 16 characters each (64 or 128 bits in length). - Each message block is then represented as a decimal number that will be encrypted. For this example, the code blocks in decimal are:
21349 25458 25972 33 - Each number is then encrypted using the RSA formula: blockE mod N. The first block will be encrypted using: 213495 mod 44377
The encrypted numbers are: 25743 38082 24556 39256 - Finally, each encrypted block is (internally) represented as a 16 bit binary number that is split into two 8 bit numbers and then displayed as the ASCII character equivalents: J&7'
Note that some ASCII characters can not be displayed which is why you might see some garbage characters or simply blank boxes.
Decrypting a Ciphertext
Decrypting a message uses the RSA decryption algorithm blockD mod N to decrypt the encryptedmessage blocks. Clicking on the Decrypt button causesthe following:
- Each encrypted code block in the Ciphertext is run through the decryption algorithm. For example, the first encrypted block: 2574335165 mod 44377
- Each decrypted block is then represented as a 16 bit binary number. This 16 bit binary number is split into two 8 bit binary numbers that represent the ASCII characters of the original message M.
- Each 8 bit number is represented as an ASCII character in the final field.
Acknowledgments
This program was inspired bythisJavaScript example of RSA designed and Rummy Makmur.( and ).
Additional Links
It turns out several other people have devloped similarapplets:Even better, if the above links are not working, just do a search on Google for "RSA demo java applet"
File: rsa_demo.html Las Update: Thu Sep 12 10:37:41 EDT 2002
All materials Copyright, 1997-2002 Richard Holowczak