Cryptography
Vjg rcrgt qp etarvqitcrja ku qrvkqpcn. Kv ecp dg wugf cu gzvtc etgfkv .
The paper on cryptography is optional. It can be used as extra credit.
Caesar cipher
From Wikipedia, the free encyclopedia.
The action of a Caesar cipher is to move each letter a number of places down the alphabet. This example is with a shift of three, so that a B in the plaintext becomes E in the ciphertext.
In cryptography , a Caesar cipher , also known as a Caesar's cipher or the shift cipher , is one of the simplest and most widely-known encryption techniques. It is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions further down the alphabet . The method is named after Julius Caesar , who used it to communicate with his generals .
The encryption step performed by a Caesar cipher is often incorporated as part of more complex schemes, such as the Vigenère cipher , and still has modern application in the ROT13 system. As with all single alphabet substitution ciphers, the Caesar cipher is easily broken and in practice offers essentially no communication security.
Vigenère cipher
The Vigenère cipher has been reinvented many times. The method was originally described by Giovan Batista Belaso in his 1553 book La cifra del. Sig. Giovan Batista Belaso , however, the scheme was later misattributed to Blaise de Vigenère in the 19th century, and is now widely known as the "Vigenère cipher".
Description
The Vigenère square or Vigenère table, also known as the tabula recta , can be used for encryption and decryption.The Vigenère cipher consists of using several Caesar ciphers in sequence with different shift values.
To encipher, a table of alphabets can be used, termed a tabula recta , Vigenère square , or Vigenère table . It consists of the alphabet written out 26 times in different rows, each alphabet shifted cyclically to the left compared to the previous alphabet, corresponding to the 26 possible Caesar ciphers. At different points in the encryption process, the cipher uses a different alphabet from one of the rows. The alphabet used at each point depends on a repeating keyword.
For example, suppose that the plaintext to be encrypted is:
ATTACKATDAWN
The person sending the message chooses a keyword and repeats it until it matches the length of the plaintext, for example, the keyword " LEMON ":
LEMONLEMONLE
The first letter of the plaintext, A , is enciphered using the alphabet in row L , which is the first letter of the key. This is done by looking at the letter in row L and column A of the Vigenère square, namely L . Similarly, for the second letter of the plaintext, the second letter of the key is used; the letter at row E and column T is X . The rest of the plaintext is enciphered in a similar fashion:
Plaintext: ATTACKATDAWN
Key: LEMONLEMONLE
Ciphertext: LXFOPVEFRNHR
Decryption is performed by finding the position of the ciphertext letter in a row of the table, and then taking the label of the column in which it appears as the plaintext. For example, in row L , the ciphertext L appears in column A , which taken as the first plaintext letter. The second letter is decrypted by looking up X in row E of the table; it appears in column T , which is taken as the plaintext letter.
Get a partner - encrypt (at least 12 characters) - trade messages - decrypt
Cryptanalysis
The Vigenère cipher is effective because it masks the characteristic letter frequencies of English plaintexts, but some patterns remain.
The strength behind the Vigenère cipher is, like all polyalphabetic ciphers, to make frequency analysis more difficult. Frequency analysis is the practice of decrypting a message by counting the frequency of ciphertext letters, and equating it to the letter frequency of normal text. For instance if P occurred most in a ciphertext whose plaintext is in English one could suspect that P corresponded to E , because E is the most frequently used letter in English. Using the Vigenère cipher, E can be enciphered as any of several letters in the alphabet at different points in the message thus defeating simple frequency analysis.
The critical weakness in the Vigenère cipher is the relatively short and repeated nature of its key . If a cryptanalyst discovers the key's length then the cipher text can be treated as a series of different Caesar ciphers , which individually are trivially broken. The Kasiski and Friedman tests help divine a ciphertext's key length.
Kasiski examination
Friedrich Kasiski published the first successful attack on the Vigenère cipher in 1863 , but Charles Babbage had already developed the same test in 1854 . Babbage decided to break the Vigenère cipher when John Hall Brock Thwaites submitted a "new" cipher to the Journal of the Society of the Arts . When Babbage showed that Thwaites' cipher was essentially just another recreation of the Vigenère cipher Thwaites grew irritated and challenged Babbage to break his cipher.
The Kasiski examination, also called the Kasiski test, takes advantage of the fact that certain common words like " the " will, by chance, be encrypted using the same key letters, leading to repeated groups in the ciphertext. For example, a message encrypted with the keyword ABCDEF might not encipher "crypto" the same way each time it appears in the plain text:
Key: ABCDEF AB CDEFA BCD EFABCDEFABCD
Plain: CRYPTO IS SHORT FOR CRYPTO GRAPHY
Cipher: CSASXT IT UKSWT GQU GWYQVR KWAQJB
The encrypted text here will not have repeated sequences that correspond to repeated sequences in the plaintext. However, if the key length is different, as in this example:
Key: ABCDAB CD ABCDA BCD ABCDABCDABCD
Plain: CRYPTO IS SHORT FOR CRYPTO GRAPHY
Cipher: CSASTP KV SIQUT GQU CSASTP IUAQJB
Then the Kasiski test is effective. The following ciphertext has several repeated segments and allows a cryptanalyst to discover its key length:
Ciphertext: DYDUXRMH TVDV NQD QNW DYDUXRMH ARTJGW NQD
The distance between the repeated DYDUXRMH s is 18. This, assuming that the repeated segments represent the same plaintext segments, implies that the key is 18, 9 or 2 characters long. The distance between the NQD s is 20 characters. This means that the key length could be 20, 10, 5 or 2 characters long (all factors of the distance are possible key lengths). By taking the intersection of these sets one could safely conclude that the key length is 2.
Simple substitution
Give example from website.
Substitution over a single letter— simple substitution —can be demonstrated by writing out the alphabet in some order to represent the substitution. This is termed a substitution alphabet .
Block Substitution (Playfair Cipher)
Arrange alphabet in 5 by 5 grid according to some pattern. Substitute digrams (2 letters at a time) as follows:
1. if in same row, use letters to the right.
2. if in same column, use letters below.
3. else, use letters in opposite corners (replace with one in its row)
A key word, MONARCHY in this example, is filled in first, and the remaining unused letters of the alphabet are entered in their lexicographic order:
Plaintext digraphs are encrypted with the matrix by first locating the two plaintext letters in the matrix. They are (1) in different rows and columns; (2) in the same row; (3) in the same column; or (4) alike. The corresponding encryption (replacement) rules are the following:
1. When the two letters are in different rows and columns, each is replaced by the letter that is in the same row but in the other column; i.e., to encrypt WE, W is replaced by U and E by G.
2. When A and R are in the same row, A is encrypted as R and R (reading the row cyclically) as M.
3. When I and S are in the same column, I is encrypted as S and S as X.
4. When a double letter occurs, a spurious symbol, say Q, is introduced so that the MM in SUMMER is encrypted as NL for MQ and CL for ME.
5. An X is appended to the end of the plaintext if necessary to give the plaintext an even number of letters.
Discussion
If the frequency distribution information were totally concealed in the encryption process, the ciphertext plot of letter frequencies in Playfair ciphers would be flat. It is not.
The deviation from this ideal is a measure of the tendency of some letter pairs to occur more frequently than others and of the Playfair's row-and-column correlation of symbols in the ciphertext. This is the essential structure exploited by a cryptanalyst in solving Playfair ciphers.
The loss of a significant part of the plaintext frequency distribution, however, makes a Playfair cipher harder to cryptanalyze than a monoalphabetic cipher.
The Vernam cipher
In modern terminology, a Vernam cipher is a cipher in which the plaintext is XORed with a random or pseudo-random stream of data the same length to generate the ciphertext. If the stream of data is truly random and used only once, this is the one-time pad . Substituting pseudorandom data generated by a cryptographically secure pseudo-random number generator is a common and effective construction for a stream cipher. RC4 is an example of a Vernam cipher that is still widely used in 2004 .
Gilbert Vernam
From Wikipedia, the free encyclopedia.
Gilbert Sandford Vernam ( 1890 – 7 February 1960 ) was a AT&T Bell Labs engineer who, in 1917 , invented the stream cipher and later co-invented the one-time pad cipher . Vernam proposed a teletype cipher in which a previously-prepared key , kept on paper tape , is combined character by character with the plaintext message to produce the cyphertext . To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext .
One-time pad
From Wikipedia, the free encyclopedia.
In cryptography , the one-time pad (OTP) is the only theoretically unbreakable method of encryption : the plaintext is combined with a random " pad " the same length as the plaintext. The "pad" part of the name comes from early implementations of the key material as a pad of gummed paper (for easy concealment, the pad was often physically very small, e.g. [1] ).
Claude Shannon showed that the one-time pad has a property known as perfect secrecy : the ciphertext gives absolutely no additional information about the plaintext . That is, the a priori probability of a plaintext message M is the same as the a posteriori probability of a plaintext message M given the corresponding ciphertext.
Despite the strong proof of security, the one-time pad has drawbacks in practice: it requires perfectly random one-time pads; secure generation and exchange of the one-time pad material, which must be at least as long as the message; and careful treatment to make sure that it is disposed of correctly and never reused — hence "one time". These implementation difficulties have led to examples of one-time pad systems being broken (for example, VENONA ), and are so serious that they have prevented the one-time pad from being adopted as a widespread tool in information security .
Example
Suppose Alice wishes to send the message 'HELLO' to Bob . Assume two pads of paper containing identical random sequences of letters were somehow previously produced and securely issued to both. Alice chooses the appropriate unused page from the pad. The way to do this is normally arranged for in advance, as for instance 'use the 12th sheet on Labor Day', or 'use the next available sheet for the next message'. The material on the selected sheet is the key for this message. Each letter from the pad will be combined in a predetermined way with one letter of the message. Every letter is given a numerical value: "A" is 0, "B" is 1, and so on through "Z", equalling 25. In this example, the technique is to combine the key and the message using modular addition . The numerical values of corresponding message and key letters are added together, modulo 26. If key material begins with,
X M C K L
and the message is "HELLO", then the coding is done as follows:
23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key
+ 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) msg
= 30 16 13 21 25 k + m
= 4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) k + m
(mod 26)
Note that if a number is larger than 25, then in modular arithmetic fashion, 26 is subtracted from the number to make it less than 26.
The ciphertext to be sent to Bob is thus "EQNVZ." Bob uses the matching key page and the same process, but in reverse, to obtain the plaintext . Here, the key is subtracted from the ciphertext, again using modular arithmetic:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) code
- 23 (X) 12 (M) 2 (C) 10 (K) 11 (L) key
= -19 4 11 11 14 c-k
= 7 (H) 4 (E) 11 (L) 11 (L) 14 (O) c-k
(mod 26)
Similar to above, if a number is negative, 26 is added to make the number positive.
Thus, Bob produces Alice's plaintext, the vital message, "HELLO". Both Alice and Bob destroy the key sheet immediately after use, thus preventing reuse and an essentially trivial attack against the cipher. The KGB often issued its agents one-time pads printed on tiny sheets of "flash paper"—paper chemically converted to nitrocellulose , which burns almost instantly and leaves no ash .
Security
Properly used one-time pads are secure in this sense even against adversaries with infinite computational power. To continue the example from above, Eve intercepts Alice's ciphertext: "EQNVZ", if Eve had infinite computing power, she would quickly find that the key: "XMCKL" would produce the plaintext "HELLO". However, she would also try the key material sequence "TQURI" giving the plaintext "LATER", an equally plausible message:
4 (E) 16 (Q) 13 (N) 21 (V) 25 (Z) cipher
- 19 (T) 16 (Q) 20 (U) 17 (R) 8 (I) key
= -15 0 -7 4 17 c-key
= 11 (L) 0 (A) 19 (T) 4 (E) 17 (R)c-key
(mod 26)
In fact, it's possible to "decrypt" any message whatsoever with the same number of characters out of the ciphertext simply by using a different key.
Controversy about one time pads in practice
Some argue that one-time pads are not practical for use in real-world systems:
• It is argued that one time pads solve few current practical problems in cryptography.
• The presence of "random number generator" functions in computer programming languages may cause users to assume they can be used to make an unbreakable encryption system using the one time pad principle. Such functions are almost always pseudorandom number generators , and cryptographically weak ones at that.
• Many vendors selling proprietary encryption schemes use "one time pad" as an advertising slogan. Such systems often fail to meet the exacting standards needed to be a true one time pad.
• The key management needed for one time pads scales badly for large networks. The number of pads required goes up as the square of the number of users exchanging messages freely amongst each other. For communication between two persons or a star network topology, this is less of a problem.
• Most of the interesting new research and applications in cryptography lie in other areas, such as public key cryptography .
But many criticisms of the one time pad apply in some degree to other cryptosystems as well:
• One time pads require a large amount of trustworthy random key material, at least equal to the total volume of messages to be sent.
• The key material must be exchanged securely between the users before sending a one-time enciphered message. Advances in data storage make this more manageable than it was in the past. Devices like CD-Rs , DVD-Rs , USB keydrives , digital cameras , and personal digital audio players all can hold large amounts of one time pad material, yet attract little suspicion.
• Both copies of the key material for each message must be kept securely until they are used.
• The key material must be securely disposed of after use, to ensure the key material is never reused and to protect the messages sent. Complete erasure that is immune to forensic recovery is a major problem, but one that applies as well to any system that stores sensitive plaintext.
• The one time pad does not provide traffic-flow security . Again this is true of any crypto system unless additional measures are taken. An eavesdropper can determine when messages are sent, their sources, destinations and message lengths, allowing traffic analysis . Techniques to reduce this vulnerability include padding , steganography , continuous transmission and secret broadcast .
The one time pad does have a couple of real advantages:
• Future mathematical breakthroughs or practical quantum computing could render systems, now considered secure, vulnerable. One time pads implemented and used properly are provably safe.
• Most encryption systems available to the public are implemented in computer software. Computer operating systems today are horribly insecure , particularly when networked. The one time pad is the only practical strong encryption system that can be implemented entirely using pencil and paper. Making the required pad material by hand is tedious, but doable for protecting short text messages between two persons. On the other hand, carrying one time pad material can get you into very serious trouble in some countries.
• Making and using a one time pad has educational value. No special equipment is required and it serves as a good introduction to cryptographic ideas.
Historical uses
In some diplomatic or espionage situations, the one-time pad is useful because it can be computed by hand with only pencil and paper. Indeed, nearly all other high quality ciphers are entirely impractical without computers. Spies can receive their pads in person from their "handlers." Embassies can receive theirs by diplomatic pouch .
One-time pads have been used in special circumstances since the early 1900s . The Weimar Republic Diplomatic Service began using the method in about 1920 . The breaking of poor Soviet cryptography by the British , with messages made public for political reasons in two instances in the 1920s , appear to have induced the USSR to adopt one-time pads for some purposes by around 1930 . KGB spies are also known to have used pencil and paper one-time pads more recently. Examples include Colonel Rudolf Abel , who was arrested and convicted in New York City in the 1950s, and the 'Krogers' (ie, Morris and Lona Cohen), who were arrested and convicted of espionage in the United Kingdom in the early 1960s. Both were found with physical one-time pads in their possession.
The U.S. and Britain used one time pad systems for their most sensitive traffic in World War II and through the 1950s . The NSA describes one time tape systems like SIGTOT and 5-UCO as being used for intelligence traffic until the introduction of the electronic cipher based KW-26 . Leo Marks reports that the British Special Operations Executive used one time pads to encode traffic between its offices. One time pads for use with its overseas agents were introduced late in the war.
The World War II voice scrambler SIGSALY was a one-time pad system. It added (analog) noise to the signal at one end and removed it at the other end. The noise was distributed to the channel ends in the form of large shellac records of which only two were made. There were both starting synchronization and longer term phase drift problems which arose and were solved before the system could be used.
In 1944 – 1945 , the US Army's Signal Security Agency was able to solve a one-time pad system used by the German Foreign Office for its high-level traffic, codenamed GEE (Erskine, 2001). GEE was insecure because the pads were not completely random — the machine used to generate the pads produced predicable output.
Beginning in the late 1940s , U.S. and U.K. intelligence agencies were able to break some of the Soviet one-time pad traffic to Moscow during WWII as a result of errors made in generating and distributing the key material. One suggestion is that Moscow Centre personnel were somewhat rushed by the presence of German troops just outside Moscow in late 1941 and early 1942, and they produced more than one copy of same key material during that period. This decades-long effort was finally codenamed VENONA (BRIDE had been an earlier name); it produced a considerable amount of information, including more than a little about some of the Soviet atom spies. Even so, only a small percentage of the intercepted messages were either fully or partially decrypted (a few thousand out of several hundred thousand).
In 1945 the U.S. discovered that Canberra - Moscow messages were being encrypted first using a code-book and then using a one-time pad. However the one-time pad used was the same one used by Moscow for Washington, DC -Moscow messages. Combined with the fact that some of the Canberra-Moscow messages included known British government documents, this allowed some of the encrypted messages to be broken.
The Cold War "hot line" between the White House and the Kremlin used a one-time pad. Providing an adequate supply of key material to cover communication in a crisis was a minor concern in comparison to the required security of messages and the reluctance of either country to reveal more sensitive cipher methods. In addition, both sides had access to all the tools of modern nations when exchanging key material: armed couriers carrying diplomatic bags , military aircraft to carry the couriers, and so on.
During the 1983 Invasion of Grenada , U.S. forces found a supply of pairs of one time pad books in a Cuban warehouse. The continued presence of number stations on shortwave radio suggests one time pads are still used by spies.
Public-key cryptography
From Wikipedia, the free encyclopedia.
Public key cryptography is a form of cryptography which generally allows users to communicate securely without having prior access to a shared secret key , by using a pair of cryptographic keys , designated as public key and private key , which are related mathematically.
The term asymmetric key cryptography is a synonym for public key cryptography.
In public key cryptography, the private key is generally kept secret, while the public key may be widely distributed. In a sense, one key "locks" a lock; while the other is required to unlock it. It should not be possible to deduce the private key of a pair given the public key.
There are many forms of public key cryptography, including:
• public key encryption — keeping a message secret from anyone that does not possess a specific private key.
• public key digital signature — allowing anyone to verify that a message was created with a specific private key.
Typically, public key techniques are much more computationally intensive than purely symmetric algorithms , but the judicious use of these techniques enables a wide variety of applications.
History
Public key cryptography was invented to address the drawbacks of key distribution — with public key cryptography, users can communicate securely over an insecure channel without having to agree upon a shared key beforehand.
The first invention [1] of an asymmetric key algorithm was by Clifford Cocks , then a recent mathematics graduate and a new staff member at GCHQ in the UK , early in the 1970s. This fact was kept secret until 1997.
The Cocks method was reinvented in 1977 by Rivest , Shamir and Adleman all then at MIT . The latter authors published their work in 1978 , and the algorithm appropriately came to be known as RSA . RSA uses exponentiation modulo a product of two large primes to encrypt and decrypt, performing both public key encryption and public key digital signature, and its security is based on the presumed difficulty of factoring large integers.
Since the 1970s, a large number and variety of encryption, digital signature, key agreement, and other techniques have been developed in the field of public key cryptography.
Applications ********
The most obvious application of a public key encryption system is confidentiality .
Public-key digital signature algorithms can be used for sender authentication . For instance, a user can encrypt a message with his own private key and send it. If another user can successfully decrypt it using the corresponding public key , this provides assurance that the first user (and no other) sent it.
These characteristics are useful for many other, sometimes surprising, applications, like digital cash .
Weaknesses
Of course, there is the possibility that someone could "pick" Bob's or Alice's lock. Unlike the case of the one-time pad or its equivalents, there is no currently known asymmetric key algorithm which has been proven to be secure against a mathematical attack .
Potential problems include:
- relation between the keys in a key pair
- weakness in an algorithm's operation
- security of asymmetric key algorithms is based on estimates of how difficult the underlying mathematical problem is to solve.
- estimates have changed both with the decreasing cost of computer power, and with new mathematical discoveries.
This might not be as weak as imagined though – because the time to decrypt the details is longer than the useful life of those details.
Recently, some attacks based on careful measurements of the exact amount of time it takes known hardware to encrypt plain text have been used to simplify the search for likely decryption keys.
Thus, use of asymmetric key algorithms does not ensure security; it is an area of active research to discover and protect against new and unexpected attacks.
Another potential weakness in the process of using asymmetric keys is the possibility of a ' Man in the middle ' attack.
This form of attack is being addressed by the development of key distribution methods that can ensure sender authenticity and message integrity , even over insecure channels.
Computational cost
Note that most public key algorithms are relatively computationally costly, in comparison with many symmetric key algorithms of apparently equivalent security.
Associating public keys with identities
Furthermore, the binding between a public key and its 'owner' must be correct, lest the algorithm function perfectly and yet be entirely insecure in practice. As with most cryptography, the protocols used to establish and verify this binding are critically important.
Who can revoke a key?
Because the principal having authority to revoke keys is very powerful, the mechanisms used to control it should involve as many participants as possible to guard against malicious attacks, while at the same time as few as possible to ensure that a key can be revoked without delay.
How to distribute a new key
After a key has been revoked, a new key must be distributed in some pre-determined manner.
Assume that Carol's key has been revoked. Until a new key has been disseminated, Carol is effectively silenced. No one will be able to send her data without violating system security, and data coming from her will be discarded for the same reason.
How to spread the revocation
The notification that a key has been revoked and should not be used again must be spread to all those that potentially hold the key, and as rapidly as possible.
Recovery from a leaked key
Assume that the principal authorized to revoke a key has decided that a certain key must be revoked. In most cases this happens after the fact; it becomes known that at some time in the past an event occurred that endangered (the secret part) of a public key. Let us denote the time at which it is decided that the compromise occurred with T.
The compromise has two implications: Messages encrypted with the public key after time T can no longer be assumed to be secret, and signatures made with the key after time T can no longer be assumed to be authentic without scrutinizing of the events leading up to where the signature being made.
RSA
From Wikipedia, the free encyclopedia.
Operation
Key generation
Suppose a user Alice wishes to allow Bob to send her a private message over an insecure transmission medium. She takes the following steps to generate a public key and a private key:
1) choose 2 large primes p & q (100 digits each?)
2) let n = p * q
3) pick e with 1 < e < (p-1)(q-1) and e is relatively prime to (p-1)(q-1)
4) find d with d*e = 1 mod (p-1)(q-1)
The public key consists of the pair n and e
The private key consists of the pair n and d
Alice transmits the public key to Bob, and keeps the private key secret. p and q are sensitive since they are the factors of n , and allow computation of d given e .
Encrypting messages
Suppose Bob wishes to send a message M to Alice. He turns M into a number m < n , using some previously agreed-upon reversible protocol known as a padding scheme .
Bob now has m , and knows n and e , which Alice has announced. He then computes the ciphertext c corresponding to m :
This can be done quickly using the method of exponentiation by squaring . Bob then transmits c to Alice.
Decrypting messages
Alice receives c from Bob, and knows her private key d . She can recover m from c by the following procedure:
Given m , she can recover the original message M . The decryption procedure works because
.
Thus,
.
A working example
Here is an example of RSA encryption and decryption. The parameters used here are artificially small, but you can also use OpenSSL to generate and examine a keypair .
We let
p = 61 — first prime number (to be kept secret or deleted securely)
q = 53 — second prime number (to be kept secret or deleted securely)
n = pq = 3233 — modulus (to be made public)
e = 17 — public exponent (to be made public)
d = 2753 — private exponent (to be kept secret)
The public key is ( e , n ). The private key is d . The encryption function is:
encrypt( m ) = m e mod n = m 17 mod 3233
where m is the plaintext . The decryption function is:
decrypt( c ) = c d mod n = c 2753 mod 3233
where c is the ciphertext .
To encrypt the plaintext value 123, we calculate
encrypt(123) = 123 17 mod 3233 = 855
To decrypt the ciphertext value 855, we calculate
decrypt(855) = 855 2753 mod 3233 = 123
Both of these computations can be done efficiently using the square-and-multiply algorithm for modular exponentiation .
Security
The security of the RSA cryptosystem is based on two mathematical problems: the problem of factoring very large numbers , and the RSA problem . Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against partial decryption may require the addition of a secure padding scheme .
No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists.
As of 2005 , the largest number factored by general-purpose methods was 663 bits long, using state-of-the-art distributed methods. RSA keys are typically 1024–2048 bits long. Some experts believe that 1024-bit keys may become breakable in the near term (though this is disputed); few see any way that 4096-bit keys could be broken in the foreseeable future. Therefore, it is generally presumed that RSA is secure if n is sufficiently large. If n is 256 bits or shorter, it can be factored in a few hours on a personal computer , using software already freely available. If n is 512 bits or shorter, it can be factored by several hundred computers as of 1999 . A theoretical hardware device named TWIRL and described by Shamir and Tromer in 2003 called into question the security of 1024 bit keys. It is currently recommended that n be at least 2048 bits long.
In 1993 , Peter Shor published Shor's algorithm , showing that a quantum computer could in principle perform the factorization in polynomial time, rendering RSA and related algorithms obsolete. However, quantum computation is not expected to be developed to such a level until at least 2015 or beyond.
==============================
2) talk about cryptology and security vs privacy issues