Public Key Cryptosystems rely on a pairs of keys assigned to each user of the cryptosystem.
RSA
- 1977, Ronald Rivest, Adi Shamir, Leonard Adleman
- RSA algorithm (Patented) form the backbone of large number of well known security infrastructure
- Computational difficulty inherent in factoring large prime numbers
- Each User of the cryptosystem generates a pair of public and private keys using the algorithm below :-
- Choose 2 large prime numbers (p and q of 200 digits length each)
- compute the product: n = p * q
- Select a number e such that
- e < n
- e and (n-1)(q-1) are relatively prime - that is, the 2 numbers have no common factors other than 1.
- Find a number d, such that (ed-1)mod(p-1)(q-1) = 0
- Distribute e and n as the public key to all cryptosystem users. Keep d secret as the private key.
- If Alice wants to send an encrypted message to Bob, she generates the ciphertext (C) from the plain text (P) using the formula (where e is Bob's public and n is the product of p and q created during the key generation process):
C = P (power e) mod n
When Bob receives the message, he performs tha following calculation ro retrieve the plaintext message:
P = C (power d) mod n
Merkle-Hellman Knapsack
- 1978
- Based on the difficulty of performing factoring operations, but it relies on a component of set theory known as super-increasing sets rather than on large prime numbers. Proven ineffective when it was broken in 1984.
Cryptosystem---------------------Key length
RSA---------------------1088 bits
DSA---------------------1024 bits
Elliptic curve---------------------160 bits
El Gamal
- Based on Diffie-Hellman key exchange algorithm
- Major Disadvantage - the algorithm doubles the length of any message it encrypts.
- This is a major hardship when encrypting long messages or data that will be transmitted over a narrow bandwidth communications circuit.
Elliptic Curve
- 1985
- Mathematicians - Neal Koblitz abd Victor Miller
- Elliptic Curve Cryptography (ECC) theory
y(power 2) = x(power 3) + ax + b
x,y,a and b are all real numbers
Hash Functions
- Take a long potentially long message and generate a unique output value derived from the content of the message.
- This value is commonly referred as message digest.
- Most cases, message digest is 128 bits or longer.
5 basic requirements
- Input can be of any length
- Output has a fixed length
- Hash function os relatively easy to compute
- Hash function is one-way . It is extremely hard to determine the input when provided with output
- Hash function is collision free (it is externally hard to find two messages that produce the same hash value)
SHA, SHA-1, SHA-2
- Government Standard hash functions developed by National Institute of Standard and Technology (NIST)
- Publication - Secure Hash Standard (SHS) aka Federal Information Processing Standard (FIPS) 180
- SHA-1 takes Input length upto 2,097,152 terabytes ----> Output 160-bit message digest
- processes a message in 512-bit blocks
- therefore it pads the Input message with additional data so that length reaches tge next highest mutiple of 512.
Recent cryptanalytic attacks demontrated weaknesses in SHA-1
Four new variants
- SHA-256 output 256-bit, 512 bit block size
- SHA-224 output 224-bit, 512 bit block size
- SHA-512 output 512-bit, 1024 bit block size
- SHA-384 output 384-bit, 1024 bit block size
MD2
- 1989
- Ronald Rivest
- 8-bit processors
- pads the message with 16 bytes
- output 16-byte checksum and appends it to the end of the message
- 128-bit message digest is then generated by using the entire original message along with the appended checksum
MD4
- 1990
- Rivest
- enhanced the algorithm to support 32-bit processors and increase the level of security
- It first pads the message to ensure that the message length is 64 bits smaller than a mutiple of 512 bits
- For example, a 16-bit message will be padded with 432 additional bits of data to make it 448 bits, which is 64 bits smaller than a 512-bit message.
- MD4 then processes 512-bit blocks in three rounds of computation to produce the message digest of 128-bit
- No longer secure
MD5
- 1991
- Rivest
- Problems again - Slow
- Subject to collisions
Hash algorithm chart
Name--------------------------------------------Hash Value Length
Hash of Variable Length(HAVAL)-an MD5 variant--------------------------------------------128,160,192,224,256
Hash Message Authenticating Code(HMAC)--------------------------------------------Variable
MD2--------------------------------------------128
MD4--------------------------------------------128
MD5--------------------------------------------128
SHA-1--------------------------------------------160
SHA-224--------------------------------------------224
SHA-256--------------------------------------------256
SHA-384--------------------------------------------384
SHA-512--------------------------------------------512
Digital Signatures
Once you have chosen a cryptographically sound hashing algorithm, you can use it to implement a digital signature system.
2 Distinct Goals
- Digitally signed messages assure the recipient that the message truly came from the claimed sender. Nonrepudiation
- Digitally signed messages assure the recipient that the message was not altered while in transit between the sender and recipient.
Process:-
- Alice generates a message digest of the original plaintext message using one of the cryptographically sound hashing algorithms, such as SHA-512.
- Alice then encrypts only the message digest using her private key. This is Digital Signature.
- Alice appends the signed message digest to the plaintext message.
- Alice sends the appended message to Bob.
Bob reverses the procedure
- Bob decrypts the digital signature using Alice's public key,
- Bob uses the same hashing function to create a message digest of the full plaintext message received from Alice.
- Bob then compares the decrypted message digest he received from Alice with the message digest he computed himself. If the 2 digests match, then he is assured that the message was only sent from Alice and also it was not modified in the transit.
Digital Signature Standard
NIST specifies the digital signature algorithms acceptable for federal government use in Federal Information Processing Standard (FIPS) 186-4, aka Digital Signature Standard (DSS)
- Digital Signature Algorithm (DSA) as specified in FIPS 186-4
- RSA algorithm as specified in ANSI X9.31
- Elliptic Curve DSA (ECDSA) as specified in ANSI X9.62
