Published on May 8, 2014
JARAMOGI OGINGA ODINGA UNIVERSITY OF SCIENCE AND TECHNOLOGY SCHOOL OF INFORMATICS AND INNOVATIVE SYSTEMS BSc. Computer Security and Forensics IIT 3218 INTRDUCTION TO NUMBER THEORY Application of Number theory in Computing GROUP MEMBERS 1.Lilian Mwende I132/0870/2013 2.Dennis Ruhiu I132/0867/2013 3.Jeremiah Kirui I132/0871/2013 4.Masinde Kenan KevinW. I132/0859/2013 5.EinsteinNyarwega I132/0879/2013 LECTURER: DR. BERNARD OKELLO
Outline Cryptography Definition of cryptography History of cryptography Cryptographic systems Uses of cryptography Types of cryptography Conclusion (future in cryptography)
INTRODUCTION Cryptography definition: Cryptography is the science of secret writing. – A cipher is a secret method of writing, where by plaintext (clear text) is transformed into a cipher text. – The process of transforming plaintext into ciphertext is called encryption. – The reverse process of transforming ciphertext into plaintext is called decipherment or decryption. – Encryption and decryption are controlled by cryptographic keys. Cypher/cipher-is a pair of algorithms that create the encryption and the reversing decryption. The detailed operation of a cipher is controlled both by the algorithm and in each instance by a "key". This is a secret usually a short string of characters, which is needed to decrypt the cipher text Cryptosystem–is the ordered list of elements of finite possible plaintexts, finite possible cypher texts, finite possible keys, and the encryption and decryption algorithms which correspond to each key. History of cryptography Before the modern era, cryptography was concerned solely with message confidentiality (i.e., encryption)—conversion of messages from a comprehensible form into an incomprehensible one and back again at the other end, rendering it unreadable by interceptors or eavesdroppers without secret knowledge (namely the key needed for decryption of that message). Encryption was used to (attempt to) ensure secrecy in communications, such as those of spies, military leaders, and diplomats. In recent decades, the field has expanded beyond confidentiality concerns to include techniques for message integrity checking, sender/receiver identity authentication, digital signatures, interactive proofs and secure computation, among others.
The earliest forms of secret writing required little more than writing implements since most people could not read. More literacy, or literate opponents, required actual cryptography. The main classical cipher types are transposition ciphers, which rearrange the order of letters in a message (e.g., 'hello world' becomes 'ehlol owrdl' in a trivially simple rearrangement scheme), and substitution ciphers, which systematically replace letters or groups of letters with other letters or groups of letters (e.g., 'fly at once' becomes 'gmz bu podf' by replacing each letter with the one following it in the Latin alphabet). Simple versions of either have never offered much confidentiality from enterprising opponents. An early substitution cipher was the Caesar cipher, in which each letter in the plaintext was replaced by a letter some fixed number of positions further down the alphabet. Suetonius reports that Julius Caesar used it with a shift of three to communicate with his generals. Atbash is an example of an early Hebrew cipher. The earliest known use of cryptography is some carved ciphertext on stone in Egypt (ca 1900 BCE), but this may have been done for the amusement of literate observers rather than as a way of concealing information. Cryptosystems. A cryptographic system has five components: – A plaintext message space, M – A cipher text message space, C – A key space, K – A family of enciphering transformations Ek: M→C. – A family of deciphering transformations DK :C→M.
M Plain text Cypher text Plaintext Dk(Ek(m))=m, for key k Cryptosystem requirements: – Efficient enciphering/deciphering – Systems must be easy to use – The security of the system depends only on the keys, not the secrecy of E or D Secure cipher Unconditionally secure: – A cipher is unconditionally secure if no matter how much ciphertext is intercepted, there is not enough information in the ciphertext to determine the plaintext uniquely. Computationally secure: – A cipher is computationally infeasible to break. EK DKC M
Secrecy Requirements -It should be computationally infeasible to systematically determine the deciphering transformation Dk from intercepted c, even if corresponding m is known. -It should be computationally infeasible to systematically determine m from intercepted c Protected Message Disallowed Message Authenticity requirements -It should be computationally infeasible to systematically determine the enciphering transformation given c, even if corresponding m is known. -It should be computationally infeasible to systematically find c’ such that Dk(c’) is a valid plaintext in M. disallowed C Ek Dk Message CEK Dk M M protected
Types of cryptography Symmetric-key cryptography Symmetric-key cryptography refers to encryption methods in which both the sender and receiver share the same key (or, less commonly, in which their keys are different, but related in an easily computable way). Symmetric key ciphers are implemented as either block ciphers or stream ciphers. A block cipher enciphers input in blocks of plaintext as opposed to individual characters, the input form used by a stream cipher. Stream ciphers, in contrast to the 'block' type, create an arbitrarily long stream of key material, which is combined with the plaintext bit-by-bit or character-by-character, somewhat like the one- time pad. In a stream cipher, the output stream is created based on a hidden internal state which changes as the cipher operates. That internal state is initially set up using the secret key material. Cryptographic hash functions are a third type of cryptographic algorithm. They take a message of any length as input, and output a short, fixed length hash which can be used in (for example) a digital signature. For good hash functions, an attacker cannot find two messages that produce the same hash. A significant disadvantage of symmetric ciphers is the key management necessary to use them securely. Each distinct pair of communicating parties must, ideally, share a different key, and perhaps each ciphertext exchanged as well. The number of keys required increases as the square of the number of network members, which very quickly requires complex key management schemes to keep them all consistent and secret. Public key cryptography Whitfield Diffie and Martin Hellman proposed the notion of public-key (also, more generally, called asymmetric key) cryptography in which two different but mathematically related keys are used—a public key and a private key. A public key system is so constructed that calculation of one key (the 'private key') is computationally infeasible from the other (the 'public key'), even
though they are necessarily related. Instead, both keys are generated secretly, as an interrelated pair. In public-key cryptosystems, the public key may be freely distributed, while its paired private key must remain secret. In a public-key encryption system, the public key is used for encryption, while the private or secret key is used for decryption. While Diffie and Hellman could not find such a system, they showed that public-key cryptography was indeed possible by presenting the Diffie–Hellman key exchange protocol, a solution that is now widely used in secure communications to allow two parties to secretly agree on a shared encryption key. Diffie and Hellman's publication sparked widespread academic efforts in finding a practical public-key encryption system. This race was finally won in 1978 by Ronald Rivest, Adi Shamir, and Len Adleman, whose solution has since become known as the RSA algorithm. Public-key cryptography can also be used for implementing digital signature schemes. A digital signature is reminiscent of an ordinary signature; they both have the characteristic of being easy for a user to produce, but difficult for anyone else to forge. Digital signatures can also be permanently tied to the content of the message being signed; they cannot then be 'moved' from one document to another, for any attempt will be detectable. In digital signature schemes, there are two algorithms: one for signing, in which a secret key is used to process the message (or a hash of the message, or both), and one for verification, in which the matching public key is used with the message to check the validity of the signature.
Cryptography's Benefits, Limitations, and Drawbacks The benefits of cryptography are well recognized. Encryption can protect communications and stored information from unauthorized access and disclosure. Other cryptographic techniques, including methods of authentication and digital signatures, can protect against spoofing and message forgeries. Practically everyone agrees that cryptography is an essential information security tool, and that it should be readily available to users. I take this as a starting assumption and, in this respect, have no disagreement with the crypto anarchists. Less recognized are cryptography's limitations. Encryption is often oversold as the solution to all security problems or to threats that it does not address. For example, the headline of Jim Warren's op-ed piece in the San Jose Mercury News reads "Encryption could stop computer crackers" . Unfortunately, encryption offers no such aegis. Encryption does nothing to protect against many common methods of attack including those that exploit bad default settings or vulnerabilities in network protocols or software -- even encryption software. In general, methods other than encryption are needed to keep out intruders. Secure Computing Corporation's Sidewinder[TM] system defuses the forty-two "bombs" (security vulnerabilities) in Cheswick and Bellovin's book, Firewalls and Network Security (Addison Wesley, 1994), without making use of any encryption . Moreover, the protection provided by encryption can be illusory. If the system where the encryption is performed can be penetrated, then the intruder may be able to access plaintext directly from stored files or the contents of memory or modify network protocols, application software, or encryption programs in order to get access to keys or plaintext data or to subvert the encryption process. For example, PGP (Pretty Good Privacy) could be replaced with a Trojan horse that appears to behave like PGP but creates a secret file of the user's keys for later transmission to the program's owner much like a Trojan horse login program collects passwords. A recent penetration study of 8932 computers by the Defense Information Systems Agency showed 88% of the computers could be successfully attacked. Using PGP to encrypt data transmitted from or stored on the average system could be like putting the strongest possible lock on the back door of a building while leaving the front door wide open. Information security requires much more than just encryption -- authentication, configuration management, good design, access controls, firewalls, auditing, security practices, and security awareness training are a few of the other techniques needed. The drawbacks of cryptography are frequently overlooked as well. The widespread availability of unbreakable encryption coupled with anonymous services could lead to a situation where practically all communications are immune from lawful interception (wiretaps) and documents from lawful search and seizure, and where all electronic transactions are beyond the reach of any government regulation or oversight. The consequences of this to public safety and social and economic stability could be devastating. With the government essentially locked out, computers and telecommunications systems would become safe havens for criminal activity. Even May himself acknowledges that crypto anarchy provides a means for tax evasion, money laundering,
espionage (with digital dead drops), contract killings, and implementation of data havens for storing and marketing illegal or controversial material. Encryption also threatens national security by interfering with foreign intelligence operations. The United States, along with many other countries, imposes export controls on encryption technology to lessen this threat. Cryptography poses a threat to organizations and individuals too. With encryption, an employee of a company can sell proprietary electronic information to a competitor without the need to photocopy and handle physical documents. Electronic information can be bought and sold on "black networks" such as Black-Net  with complete secrecy and anonymity -- a safe harbor for engaging in both corporate and government espionage. The keys that unlock a corporation's files may be lost, corrupted, or held hostage for ransom, thus rendering valuable information inaccessible. When considering the threats posed by cryptography, it is important to recognize that only the use of encryption for confidentiality, including anonymity, presents a problem. The use of cryptography for data integrity and authentication, including digital signatures, is not a threat. Indeed, by strengthening the integrity of evidence and binding it to its source, cryptographic tools for authentication are a forensic aid to criminal investigations. They also help enforce accountability. Because different cryptographic methods can be employed for confidentiality and authentication, any safeguards that might be placed on encryption to counter the threats need not affect authentication mechanisms or system protocols that rely on authentication to protect against system intrusions, forgeries, and substitution of malicious code.
Implementation SHA1 in cryptography SHA-1 hashing is also used in distributed revision control systems like Git, Mercurial, and Monotone to identify revisions, and to detect data corruption or tampering. These are examples of SHA-1 message digests in hexadecimal and in Base64 binary to ASCII text encoding SHA1 ("The quick brown fox jumps over the lazy dog") Gives hexadecimal: 2fd4e1c67a2d28fced849ee1bb76e7391b93eb12 Gives Base64 binary to ASCII text encoding: L9ThxnotKPzthJ7hu3bnORuT6xI= Even a small change in the message will, with overwhelming probability, result in a completely different hash due to the avalanche effect. For example, changing dog to cog produces a hash with different values for 81 of the 160 bits SHA1 ("The quick brown fox jumps over the lazy cog") gives hexadecimal: de9f2c7fd25e1b3afad3e85a0bd17d9b100db4b3 gives Base64 binary to ASCII text encoding: 3p8sf9JeGzr60+haC9F9mxANtLM= SHA-1 pseudo code h0 = 0x67452301 h1 = 0xEFCDAB89 h2 = 0x98BADCFE h3 = 0x10325476 h4 = 0xC3D2E1F0
ml = message length in bits (always a multiple of the number of bits in a character). Pre-processing: append the bit '1' to the message i.e. by adding 0x80 if characters are 8 bits. append 0 ≤ k < 512 bits '0', thus the resulting message length (in bits) is congruent to 448 (mod 512) append ml, in a 64-bit big-endian integer. So now the message length is a multiple of 512 bits. Process the message in successive 512-bit chunks: break message into 512-bit chunks for each chunk break chunk into sixteen 32-bit big-endian words w[i], 0 ≤ i ≤ 15 Extend the sixteen 32-bit words into eighty 32-bit words: for i from 16 to 79 w[i] = (w[i-3] xor w[i-8] xor w[i-14] xor w[i-16]) leftrotate 1 Initialize hash value for this chunk: a = h0 b = h1 c = h2 d = h3 e = h4 Main loop: for i from 0 to 79 if 0 ≤ i ≤ 19 then f = (b and c) or ((not b) and d) k = 0x5A827999 else if 20 ≤ i ≤ 39 f = b xor c xor d
k = 0x6ED9EBA1 else if 40 ≤ i ≤ 59 f = (b and c) or (b and d) or (c and d) k = 0x8F1BBCDC else if 60 ≤ i ≤ 79 f = b xor c xor d k = 0xCA62C1D6 temp = (a leftrotate 5) + f + e + k + w[i] e = d d = c c = b leftrotate 30 b = a a = temp Add this chunk's hash to result so far: h0 = h0 + a h1 = h1 + b h2 = h2 + c h3 = h3 + d h4 = h4 + e Produce the final hash value (big-endian) as a 160 bit number: hh = (h0 leftshift 128) or (h1 leftshift 96) or (h2 leftshift 64) or (h3 leftshift 32) or h4
Conclusion Cryptography as a field has a bright future, with new research and development prompting new algorithms and methods. Quantum computing, perhaps the next, largest step in computing, also provides the newest hopes for cryptography, creating the potential for new cryptographic methods an algorithms, obsolescing modern applications and algorithms at the same time. By looking at modern and past methods cryptographers can look to the future with experience, creating better, more efficient algorithms without recreating the mistakes of the past.
References 1.Cryptographic techniques (pdf) - C.H.HUANG 2.Cryptography in C and C ++ - Michael Welschenbach 3. Cryptography and Data Security, Elizabeth and R. Denning, Purdue University, 1998 4. ØFAQ about Today’s Cryptography, RSA Laboratory, (found in www.rsa.com) 5. Future in cryptography 6. A. Shamir. "How to share a secret." In Communications of the ACM, volume 22, pp. 612–613, ACM, 1979. 7.The future of cryptography by Dorothy E. Denning, Internet security review The Future of Cryptography
Cryptography or cryptology (from ... be broken even with unlimited computing power—an example is the one ... that have some application in cryptography ...
History of cryptography ... and the subsequent introduction of electronics and computing has allowed elaborate ... The discovery and application, ...
Cryptography is a method of storing and transmitting data in a particular form so that only ... Cloud Application Testing; Cloud Computing Testing and ...
This topic includes a series of brief sections that provide information to help you decide if the Cryptography Application Block is suitable for your ...
4 Application: RSA cryptography There are many interesting applications of number theory and abstract al-gebra, especially in computer-related subjects.
... research group and the Centre for Parallel Computing ... background in network security and/or applied cryptography. ... application (at) cispa ...
1. jaramogi oginga odinga university of science and technology school of informatics and innovative systems bsc. computer security and ...
Cryptography Policy and the Information Economy Matt Blaze AT&T Labs – Research 600 Mountain Avenue Murray Hill, NJ 07974 908-582-5524 firstname.lastname@example.org
Guide to Cryptography. From OWASP. ... as computing power increases the feasibility of ... A web application can implement cryptography at ...