Plaintext = ( ciphertext^d ) mod n To generate private (d,n) key using openssl you can use the following command: openssl genrsa -out private.pem 1024 To generate public (e,n) key from the private key using openssl you can use the following command: openssl rsa -in private.pem -out public.pem -pubout.
< Cryptography
The elementary working of Public Key Cryptography is best explained with an example. The working below covers the making of simple keys and the encryption and decryption of a sample of plain text. By necessity, the example is greatly simplified.
Basic Public Key Summary[edit]![]()
![]()
Figure 1: Bob knows Alice's public key and uses it to encrypt the message. Alice uses her private key to decrypt the message.
Making Site B's PUBLIC Key[edit]
A public key is available to all, and is used to encrypt messages that are being sent to the key's owner.
To illustrate the point for an intending recipient, let us make a simple example with the large prime numbers replaced with very small ones.
Say the two secretly held prime numbers are:
Then the modulus of the arithmetic that will be used is given by their product:
The encryption key can be found as follows:First, using the two prime numbers, calculate the function:
then,
Select ANY number that is relatively prime to f(n) and less than it.
(Two numbers are said to be relatively prime when they share no common factors other than one. This term is also referred to as mutually prime, or coprime).
The receiving site's PUBLIC key can then be safely given to the world as :
The actual size of the numbers used is very large. For example, for a 1024-bit RSA encryption, this number is the size in bits of the modulus; this is equivalent to a decimal number of about 308 digits, or 256 hex digits. The public exponent most often chosen has an integer value of 65537. This exponent is chosen because it produces faster encryption than some other selections; that is, because of its large zero count in the binary form (10000000000000001), it lends itself to fast processing with binary shifting methods. It is known elsewhere as Fermat number F4. Despite this preference for the same exponent, recall that the other part of the public key set is the modulus, and that will differ between users based on the very large number of primes available.
Making Site B's Private KEY[edit]
Used by Site B when decrypting messages that were sent to them, encrypted using Site B's public key.
The private key pair is used to decrypt messages, and this key will only work if the public key of the same site was used to encrypt the message. That is to say, Site B's public key is obtained from a directory, then used by Site A to encrypt a message for them. When the message gets to Site B, Site B uses its own private key for decryption.
Continuing with the simple example above, the private key of Site B is made from its public key as follows.
private decrypt exponent = (public encrypt exponent)-1 Mod f(n)
∵ public encrypt exponent = 7 , and f(n) = 40 ∴ (private decrypt exponent x 7) Mod 40 = 1 ∴ private decrypt exponent = 23 The Site B PRIVATE key pair is then: (23,55) as (decryption exponent, modulus)
It will have been noted by some that the same number can result for both the encrypt and decrypt exponents. This particular case must be avoided by deliberate testing since a hacker would likely test for this possibility early in the process of an attack. In the above examples, this would have been the case if 9, 11, 21, 33 or 39 were chosen for the public key instead of some other. Lest it be thought that anticipation of this error is simple, notice that even in this set that both coprimes that are themselves prime (eg; leading to: 11 * 11 = 1 mod 40), and those that are coprime but not in themselves prime (eg; 9, 21, 33, and 39), can all produce this insecure state of affairs.
With the use of long primes, m the modulus (their product), is very much longer, but it should be apparent that an intending hacker could still obtain the private key if he were able to find the two secret primes as a starting point. Both the public key and the modulus to use with it are given to all who require it for encryption, so the burden of a mathematical attack reduces to the difficulty of factoring the modulus into these two secret primes. For the simple example shown above (m=55) this task is very simple, but for a very large number this effort is prohibitively long.
The native format in which the private key is delivered is in fact base-64, (a character set that needs only 6 bits per character, instead of the 4 for hex or the 7 for ASCI character codes). Unlike the public key string, the layout of a practical private key string for a 1024-bit RSA encryption contains the private key details, the public key details, and the secret numbers used in their making, as well as various other numbers and headers. The private key exponent, unlike the public exponent, is quite long, and is the equivalent of 256 hex digits in length. The secret primes are each 128 hex numbers in length. The decimal equivalent lengths are 308 digits for the private exponent (and the modulus), and 154 digits for each of the secret numbers.
Factoring the Modulus[edit]Hackers who intend to factor the modulus without any other algorithm to assist, can simply divide the modulus by a succession of increasing primes until a zero remainder results. Then the two primes would be known. However the number of primes is also very high in such a large modulus. In general the following approximation, referred to as The Prime Number Theorem, gives the number of primes in the number x as:
number of primes ≅ x/(logx - 1)
now a 64 bit space is equivalent to about 20 digits ∴ number of primes ≅ 4 * 1017 then assuming 1 million calculations per second, (a wildly optimistic assumption for most): the time to test all the primes ≅ 13,500 years
The example here was limited to 64 bits because the more representative figures, 128, 256, 512, 1024, and 2048-bit calculations are too big for most calculators. See The Math Behind Estimations to Break a 2048-bit Certificate by DigiCert for more details.
This example does not consider the use of improved methods for factoring, and these appear frequently in the literature. At present, (2014), the best of these is considered to be the General Number Field Sieve (GNFS), used to establish the record in December 2009.
To expand a little on the subject of improved methods, it will be apparent that starting with lists of tabulated primes speeds up the process. This, and the production of calculated product tables against their future need also allows much faster processing than would otherwise be possible by calculating on the fly. Because clearly, for a large set of such cracking problems, half of the solutions will lie in the first half of the trial values and half of them in the second, it has become the habit to express the expected time to solution for half of the set as opposed to the whole number implied by the Prime Number Theorem.
Encryption with B's Public Key[edit]
Assume that the public key pair belong to a Site B. Assume also that a plain language character represented by the number '2' is to be encrypted by Site A and sent to the recipient Site B: Site A uses Site B's public key pair to do so.
Assume plaintext=2
cyphertext = plaintext public encrypt exponent Mod n ∵ public encrypt exponent =7, and modulus = 55 ∴ cyphertext = 27 Mod 55 = 128 Mod 55 ∴ cyphertext = 18
With the very small numbers used in the example the cracking of the code would be relatively simple. But for very large values of primes p and q, and without knowing the private key value, the burden becomes very difficult. In some cases the task would involve an unreasonable time even for a very large number of computers.
Public key encryption does not disguise the relative frequency of the characters used. This is considered a failing in such systems since it improves the chances of cracking the code. So, the plaintext characters are arranged into groups before encryption to hide their natural frequencies of use; the groups are very large, the limit being that the size of a number encrypted must be smaller than the modulus in use.
Decryption with B's Private Key[edit]
Decryption using the above specific example is acheived as follows:For the received cyphertext = 18
With cyphertext=18 from previous section
Plaintext = cyphertextprivate decrypt exponent Mod n ∵ private decrypt exponent = 23, and modulus = 55 ∴ Plaintext = 1823 Mod 55 = 74347713614021927913318776832 Mod 55 ∴ Plaintext = 2 (You can only just confirm this with the Windows scientific calculator) Private Public Key Generator With Mod Download
Notice that the plain language value of 2 has been recovered, which is the required result.
Exceptions[edit]
Some attempts with other than the correct private key will be nonetheless successful. There are exceptions that need to be considered. For example, in the above case, using the decrypt exponent =3 will also produce the correct result. See below:
With cyphertext=18 from previous section
Plaintext = cyphertextprivate decrypt exponent Mod n ∵ hacker's attempted decrypt exponent = 3, and modulus = 55 ∴ Plaintext = 183 Mod 55 = 5832 Mod 55 ∴ Plaintext = 2 also the right result. Note that every (N^7Mod55)^3Mod55 (N^7Mod55)^23Mod55)
In a practical environment further consideration would be given to such matters in the selection of keys.
The Internet Speed Compromise[edit]
Because public key encryption and decryption is so very slow, it is unsuitable in its native form for internet use. In fact, asymmetric public key encryption is used for only a small part of internet communications. Such systems are hybrid. The summary of the method used is as follows:
The systems currently in use for internet browsers are Transport Layer Security (TLS) and its predecessor, Secure Sockets Layer (SSL). A complete description of these is available at Wikipedia's Secure Sockets Layer.
Note that in a duplex system, that is, the usual kind that sends in both directions, there will be two such procedures. One originated at each end. The key sets used for send and receive, for both asymmetric and symmetric encryption systems are all different.
Message Authentication[edit]
Security breaks down if outsiders can change the message in transit, or if they mis-represent themselves right from the start. In an attempt to overcome these risks digital certificates were devised. In a further attempt to ensure that the certificates were from the place respected by the users, the certificates were given digital signatures. One such method among many is the Digital Signature Algorithm (DSA), the basis of the Digital Signature Standard (DSS).
These certificates are not just simple text messages, which of course could be imitated, but use calculated values based on the content of a message. The entire basis of certification depends both on the designed properties of these hash algorithms and on the integrity of those who assert their worth. Their properties include:
The hash value is calculated by the sender and compared with one calculated at the receiving end, where the two must match for acceptance. Like encryption itself, hash values are too laborious to reverse engineer, that is to say, new or changed messages could not be made by outsiders to represent an existing hash value within any useful time period. Because of this they provide a basis upon which to verify that a message's contents were not changed since the certificate was issued.
Certificates themselves are tested against known root certificates within the browser store, to ensure that the certificates are from a known reliable source. If certificates are secret-signed with a private key known only to the issuing authority, then validation of the certificate can be made by decrypting the signature with its public key. That is to say, because the process is reversible, validation of the source can be made.
The actual process used for these tasks is more complex than is implied in summary, involving many long-bit calculations, but the strength of the system is unlikely to satisfy the skeptical until the sums are seen. Refer to the pdf file How Encryption and Digital Signatures Work and read the section An Example of a Digital Signature Mechanism for such a description.
The process of testing certificates and other matters are in any case summarized by browsers for their users. Browsers will indicate clearly whether or not they consider a connection to be secure. The most common of these indications includes an added padlock somewhere on the screen and the modification of the site's http address heading to read https. Some browsers such as Opera add other information such as color coding to represent the levels of security.
Private Public Key Generator With ModelsSee also[edit]
Private Public Key Generator With ModeFurther reading[edit]
Private Public Key Generator With Mod 1
Retrieved from 'https://en.wikibooks.org/w/index.php?title=Cryptography/A_Basic_Public_Key_Example&oldid=3663590'
Comments are closed.
|
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
November 2020
Categories |