# Cryptology and Number Theory

## Cryptology and Number Theory

### Cryptology and number theory (Forensic Science)

Cryptology encompasses both cryptography, the hiding of messages, and cryptanalysis, the revealing of hidden messages. Number theory is involved in cryptography in many ways, but its most important use is in public-key encryption.

A number of computationally intensive algorithms exist in number theory, one of which is factoring the product of two large prime numbers. In 1978, Ron Rivest, Adi Shamir, and Leonard Adleman published a public-key encryption algorithm named RSA (from the initials of the inventors’ last names) that uses the difficulty of factoring large numbers to protect the value of a private key. RSA has been used to encrypt electronic files to ensure their confidentiality and to create digital signatures for e-mail to ensure its integrity.

When computer hackers want to see encrypted files, they often devise attacks to steal the receivers’ private keys, which will allow them to decrypt the files. When such attacks occur, forensic experts can use tools designed to detect the attacks; similar tools are available to defend against such attacks. Hackers recognize that digital signatures can be used to guarantee the integrity of e-mail. They often intercept e-mail messages, modify the contents, and then attach invalid signatures. The hackers then have to ensure that the receivers use fake public keys to check the signatures. One way hackers could do this would be by replacing certificate authorities’ public keys in the...

(The entire section is 244 words.)

### Encryption and Number Theory (Forensic Science)

Encryption is the process of using a key to transform a readable plaintext message into an unreadable ciphertext message. Decryption reverses encryption to recover the plaintext message. When the encryption and decryption key are the same, the encryption is described as algorithm-symmetric. Although symmetric algorithms are complex, they do not use much number theory.

Public-key encryption algorithms, which are often based on number theory, use different keys for encryption and decryption. The most famous public-key encryption algorithm, RSA, selects two large prime numbers (a prime number is divisible only by one and by itself) and forms a modulus, n, as their product. The modulus n is too large to be factored. The ciphertext message, C, is created by raising the integer value of the plaintext message, M, to the power e modulo n, and the plaintext message is recovered from C by raising C to the power d modulo n. The public key is the pair (e, n) and the private key is the pair (d, n).

RSA is widely used for encrypting files and signing messages. It has proven to be very resistant to brute-force attacks on the private keys. A major part of the RSA scheme involves creation of the private keys and the safe distribution of the corresponding public keys. Usually, the private key is...

(The entire section is 254 words.)

### Computer Hacking and Encryption (Forensic Science)

In 1976, Whitfield Diffie and Martin Hellman developed an algorithm that allowed two people to create a shared symmetric key. The algorithm is similar to the RSA public-key algorithm and makes considerable use of modular exponential arithmetic. To create the shared symmetric key, each person involved uses a secret number that never leaves his or her computer but generates the shared secret key as the result of several data exchanges. If a hacker knows that a purchaser and an online store are generating a symmetric key with the Diffie-Hillman key exchange, the hacker could drop a Trojan horse into the purchaser’s computer, capture the secret information, and then masquerade as the purchaser to buy items for personal gain. In investigating such an attack, a forensic expert could log into the purchaser’s computer and check to see if the Trojan horse is still there; if it is, it might provide information on the location of the hacker.

Hackers can gain access to other people’s computers in a number of ways, not the least of which is through Web browsers. When they gain access, they often try to leave files that contain worms, Trojan horses, or viruses. Given these threats, computers have become increasingly well equipped with antivirus software that is designed to protect users from such attacks. One of the most important techniques used by antivirus software is to check all files and quarantine any files...

(The entire section is 309 words.)

Hellman, Martin. “An Overview of Public Key Cryptography.” IEEE Communications Magazine, May, 2002, 42-49. Very good survey article provides basic information. Written by one of the founders of the field of public key encryption.

Mandia, Kevin, Chris Prosise, and Matt Pepe. Incident Response and Computer Forensics. 2d ed. Emeryville, Calif.: McGraw-Hill/Osborne, 2003. Includes several chapters on incident response to cryptology attacks.

Shieneier, Bruce. “Inside Risks: The Uses and Abuses of Biometrics.” Communications of the ACM 42 (November, 1999): 136. Brief but informative article describes methods of defeating encryption by subversion.

Shinder, Debra Littlejohn. Scene of the Cybercrime: Computer Forensics Handbook. Rockland, Mass.: Syngress, 2002. Bridges the gap between the computer professionals who provide the technology for cybercrime investigations and the law-enforcement professionals who investigate the crimes.

Vacca, John R. Computer Forensics: Computer Crime Scene Investigation. 2d ed. Hingham, Mass.: Charles River Media, 2005. Provides a good introduction to computer forensics. Devotes several chapters to cryptology forensics.

Yan, Song Y. Cryptanalytic Attacks on RSA. New York: Springer, 2008. Covers most of the known cryptanalytic attacks and defenses of the RSA cryptographic system. Also provides a good introduction to...

(The entire section is 190 words.)

## Cryptology and Number Theory (World of Forensic Science)

Forensic analyses can be concerned with unraveling the true meaning of deliberately convoluted communications. Forensic accounting can involve the search of seized financial and other paper and computer records. An examiner may encounter information that has been altered so as to be indecipherable. Understanding the nature of the informational alteration can permit descrambling strategies to be applied, rendering the information understandable.

Cryptography is a division of applied mathematics concerned with developing schemes and formula to enhance the privacy of communications through the use of codes. More specifically, cryptography is the study of procedures that allow messages or information to be encoded (obscured) in such a way that it is extremely difficult to read or understand encoded information without having a specific key (i.e., procedures to decode) that can be used to reverse the encoding procedure.

Cryptography allows its users, whether governments, military, businesses or individuals, to maintain privacy and confidentiality in their communications. The goal of every cryptographic scheme is to be "crack proof" (i.e., only able to be decoded and understood by authorized recipients). Cryptography is also a means to ensure the integrity and preservation of data from tampering. Modern cryptographic systems rely on functions associated with advanced mathematics, number theory that explores the properties of numbers and the relationships between numbers.

Encryption systems can involve the simplistic replacement of letters with numbers, or they can involve the use of highly secure "one-time pads" (also known as Vernam ciphers). Because one-time pads are based upon codes and keys that can only be used once, they offer the only "crack proof" method of cryptography known. The vast number of codes and keys required, however, makes one-time pads impractical for general use.

Many wars and diplomatic negotiations have turned on the ability of one combatant or country to read the supposedly secret messages of its enemies. The use of cryptography has broadened from its core diplomatic and military uses to become of routine use by companies and individuals seeking privacy in their communications. Governments, companies, and individuals require more secure systems to protect their databases and e-mail.

In addition to improvements made to cryptologic systems based on information made public from classified government research programs, international scientific research organizations devoted exclusively to the advancement of cryptography, such as the International Association for Cryptologic Research (IACR), began to apply applications of mathematical number theory to enhance privacy, confidentiality, and the security of data. Applications of number theory were used to develop increasingly involved algorithms (i.e., step-by-step procedures for solving a mathematical problems). In addition, as commercial and personal use of the Internet grew, it became increasingly important, not only to keep information secret, but also to be able to verify the identity of message sender. Cryptographic use of certain types of algorithms called "keys" allow information to be restricted to a specific and limited audience whose identities can be authenticated.

In some cryptologic systems, encryption is accomplished, for example, by choosing certain prime numbers and then products of those prime numbers as the basis for further mathematical operations. In addition to developing such mathematical keys, the data itself is divided into blocks of specific and limited length so that the information that can be obtained, even from the form of the message, is limited. Decryption is usually accomplished by following an elaborate reconstruction process that itself involves unique mathematical operations. In other cases, decryption is accomplished by performing the inverse mathematical operations performed during encryption.

In the late 1970s, government intelligence agencies, and Ronald Rivest, Adi Shamir, and Leonard Adleman, published an algorithm (the RSA algorithm) destined to become a major advancement in cryptology. The RSA algorithm underlying the system derives its security from the difficulty in factoring very large composite numbers. The RSA algorithm was the mathematical foundation for the development of a public two-key cryptographic system called Pretty Good Privacy (PGP).

Applications of number theory allow the development of mathematical algorithms that can make information (data) unintelligible to everyone except for intended users. In addition, mathematical algorithms can provide real physical security to datallowing only authorized users to delete or update data. One of the problems in developing tools to crack encryption codes involves finding ways to factor very large numbers. Advances in applications of number theory, along with significant improvements in the power of computers, have made factoring large numbers less daunting.

In general, the larger the key size used in a system, the longer it will take computers to factor the composite numbers used in the keys.

Specialized mathematical derivations of number theory such as theory and equations dealing with elliptical curves are also making an increasing impact on cryptology. Although, in general, larger keys provide increasing security, applications of number theory and elliptical curves to cryptological algorithms allow the use smaller keys without any loss of security.

Advancements in number theory are also used to crack important cryptologic systems. Attempting to crack encryption codes (the encryption procedures) often requires use of advanced number theories that allow, for instance, an unauthorized user to determine the product of the prime numbers used to start the encryption process. Factoring this product is, at best, a time consuming process to determine the underlying prime numbers. An unsophisticated approach, for example, might be to simply to attempt or apply all prime numbers. Other more elegant attempts involve algorithms termed quadratic sieves, a method of factoring integers, developed by Carl Pomerance, that is used to attack smaller numbers, and field sieves, algorithms that are used in attempts to determine larger integers. Advances in number theory allowed factoring of large numbers to move from procedures that, by manual manipulation, could take billions of years, to procedures thatith the use of advanced computingan be accomplished in weeks or months. Further advances in number theory may lead to the discovery of a polynomial time factoring algorithm that can accomplish in hours what now takes months or years of computer time.

Advances in factoring techniques and the expanding availability of computing hardware (both in terms of speed and low cost) make the security of the algorithms underlying cryptologic systems increasingly vulnerable.

These threats to the security of cryptologic systems are, in some regard, offset by continuing advances in design of powerful computers that have the ability to generate larger keys by multiplying very large primes. Despite the advances in number theory, it remains easier to generate larger composite numbers than it is to factor those numbers.

Other improvements related to applications of number theory involve the development of "nonreputable" transactions. Non-reputable means that parties cannot later deny involvement in authorizing certain transactions (e.g., entering into a contract or agreement). Many cryptologists and communication specialists assert that a global electronic economy is dependent on the development of verifiable and nonreputable transactions that carry the legal weight of paper contracts. Legal courts around the world are increasingly being faced with cases based on disputes regarding electronic communications.

SEE ALSO Codes and ciphers; Computer forensics; Computer hardware security; Computer security and computer crime investigation; Computer software security; Decryption.