Public key cryptography

8 minute read

Updated:

5. Public key cryptography

Source code for this post can be found at:
View Source code - MAC

Last time

  • MAC – ways of helping us guarantee the integrity w/o the confidentiality - We use hash function = combo of secret info + msg and hash it output is a fixed sized hash good way of checking that the msg hasn’t changed
    • Hash function is sensitive to changes
  • Merkle Damgard method is vulnerable to length extension attacks, as you can tamper without knowing the secret use HMAC where you hash twice
  • Hash function – resistant to collisions. It will always happen but we needa make it hard
  • Old hash methods are easier to find collisions
    • Recent e.g – when you hash using md5, the same 2 hello program, it hashes to same value!!
  • SHA256 – more prone to attacks

Objectives

  • Understand the basic principles underlying Public Key Cryptography (PKC)
  • Appreciate differences between PKC and symmetric ciphers
  • Recognise the applications of PKC to key distribution and message authentication
  • Asymmetric cipher – uses DIFFERENT keys to encrypt and decrypt.

Introduction to Public Key Cryptography - PKC

  • We use 2 different keys – a public key (+) and a private key (-)
  • Is based on number theory, not bit manipulation
    • Prime numbers and factorisation, etc
  • We find the key size to be pretty big, but this doesn’t mean that it is more secure.
  • Don’t think that AES is gonna make the symmetric obsolete. (not needed) we need both!! below

PKC scenario

  • Alice is tryna send a msg to bob
  • Alice has a plaintext p, and key KB+ uses bob’s public key!!, which yields a cipher text C
    • But bob the only person who can decrypt that using his private key
  • Send it to Bob
  • Bob has cipher text and his private key
  • Bob can use the private key to decrypt the original msg
  • Eve is capturing the cipher text, but she can’t do anything coz she can only see the public key of bobs.
    • If bob is the only person who knows & the key is big enough to be resistant to brute forcing safe

Requirements

  • What do we need for this to work?
    • Easy to encrypt for that person, given the public key
    • Easy for that person to decrypt given their private key
    • Very very diff to determine priv from pub
    • Hard to recover the plaintext given public key and cipher (w/o priv key)
  • We have many diff approaches—RSA, ElGamal, ECC

PKC algorithms

  • What they have in common is they are all based on a problem that is mathematically intractable to solve in the absence of certain piece of information
    • So if we hide this piece of info, no one can decrypt it.

  • RSA- about factoring large number

  • ElGamal- computing discrete log

    • Victorious – Moscow’s online voting system using El Gamal, but the key size was too small so the priv key could be determined within 20 min wtf lol – figured before the vote so now its 1024 bits
  • ECC- about elliptic curve
    • It gives smaller key size, but same level of protection as RSA
    • Smart cars – advantageous to have small keys. But w quantum computing - ECC will be easiest to crack
    • Cautious because of Edward Snowden – leaked about NSA
      • Suggestion in this doc that NSA deliberately weakened ECC?

RSA Algorithm

  1. Select prime numbers p and q
  2. We multiply them to calculate n = pq
  3. We calculate Euler totient of n, φ(n) which is the product of p-1, q-1
    1. φ(n) = (p-1)(q-1)
  4. Select integer e, so that the greatest common divisor of e and Euler totient is 1
    1. Must be greater than 1, but less than Euler, and no common divisor
  5. Calculate another integer d, such that d*e modular φ(n) = 1
    1. Modulo 10 = can be range from 0, 9 but if it hits 10, back to zero
  • Now we have n, e, d
    • Combination of {e,n} public key
    • Combination of {d,n} private key
    • So they are interloped as they were derived from the same set
  • Given those values, you can now do encrypt and decryption, which is
    • image
    • Encryption is we take plain text P, raise it to e, then do modulo n = cipher!!
    • Decryption is we take cipher text C, raise it to d, do modulo n = plain text!
      • Q: But how do you increase the plain text by e??????
        • A: Text corresponds to bit pattern. Convert hello binary integer
        • So take a piece of text, and raise it to a power by changing it to a numerical value
  • Fact that we do modulo n, we are limited to size of the chunk of bit – it we have longer text, we need to spilt it into diff blocks.
    • N= 1000 bit, we cant do no more than 1000 bits. But how fast is this gonna be?

RSA Example

  1. Select two prime number
    1. p = 17, q=11
  2. Calculate the product
    1. n = 17* 11= 187
  3. Euler totient
    1. φ(n) = (p-1)(q-1)
    2. φ(n) = 16*10 = 160
  4. Choose integer e
    1. e = 7
  5. Determine value of d such that
    1. d*e modular φ(n) = 1
    2. 7d mod 160 = 1, so first possible value is 7d= 161, d = 23.
      1. 160/7 = 22.32535 so 23. 23*7 = 161. 161 mod 160 =1
  • Public key and private key as a pair
  • image
    • Doesn’t work for all possible values
    • encrypt(187) = 0. Decrypt(0) = broken
    • There’s a limited range of possible values you can encrypt in one go which is determined by the size of n. so you need to have big n

Attacking RSA

  • Brute force search is possible for all private keys
    • If d and n is large enough, we are safe, but it will be incredibly slow!
  • We can try to get the original prime factor of n, which is smarter. if you can factorize n, you can find the keys.
    • Generated sets of RSA numbers varying from size, and they set the challenge of ppl factorising this successfully

RSA Number examples

  • image
  • Name use dot be after the digits but is now by its bits.
  • RSA 1024, 2048 hasn’t been factorized yet.
  • What does it mean to be factorized?
    • If you can factorize it, it means that you have the recipe for finding the keys.

RSA-768

  • Find 2 prime numbers, multiplied together will yield that number! which for 768 is incredibly long
  • 1024 is going to be 1000 times harder, but will be able to in decades
  • GPU, FPGA, clouds with increasing computing power, ull be able to do this in a powerful way in ur pc!

Applications of PKC

  • So, we could use this general encryption and decryption and I can use public key for someone to encrypt sth, and we never have to exchange keys solving the problem of symmetric ciphers of having to share a key.
  • Q: Don’t need to share a key in asymm! But then why do we need symmetric?
    • Dotnet run AES CBC 10000000 = 0.014 sec
    • Dotnet run 10000000 = 6.479 sec
    • RSA is good, but its WAY SLOWER!!!!!!!!!! we can’t use it for large chunks of data. Hence not a replacement
  • Together – use RSA to encrypt the shared key that’s used for AES (symmetric),
  • Use public key techniques to securely exchange the session key, which is then used for symmetric cipher.
  • Basis of everything you do in HTTPs url
  • Public key cipher as a way of securely exchanging session key, then AES

Digital Signatures

  • So far we’ve talked about using public key and encrypting sth so that only the person w/ private key can decrypt it. cipher
  • BUTT What if we encrypt it with priv key, and decrypt with public key!! But everyone knows public key useless confidentiality
  • However, if you successfully decrypted it with a public key, you know the person who encrypted it, has the priv key ensuring authenticity and integrity
  • So what we could do is take all our msgs, sign it with digital signature by encrypting them with private key, and decrypt with public key. too slow, so we don’t but since its slow we do it with hash.
    • We can compute a hash of any file, and this hash can be efficiently encrypted with priv key. Now to verify the signature, we decrypt with public key, make sure the hash value is the same as the computed hash value.
  • Know the difference between cipher and dig signing
    • Cipher to encrypt using public key, decrypt private key
    • Digital signing – the other way around

Key management Issues

  • We can use pub key to help us exchange shared key to use it in apps, BUT, that only works if you trust the public key have to verify the public key!!
  • what certificates are for! have a third party to verify it
    • U assume you trust the third party, then you know that ur public key is genuine.

Public Key Certificates

  • Take public key and have other organisation (certificate authority) to sign it using their private key.
    • If you assume you trust the third party, then you know that ur public key is genuine.
  • To what extent can you trust the third party tho?

TLS certificate Validation - How do we know that a public key is valid?

  • Domain level – checking the right to administratively manage a domain name
  • Organisation – domain level validation + organization’s actual existence as a legal entity
  • Extended – must persuade the certificate provider of its legal identity
    • Troy Hunt says: no point, as it is more of a selling technique that tricks the company and users
  • Is it worthwhile to do extra certification like this?

X.509

  • Part of X.500 standards, which define various directory services for networked systems.
  • Provides a standard public key infrastructure (PKI)
    • Repository for public key certificates
    • Authentication protocols using certificate
    • Chaining of certificates
    • Procedure for certificate revocation

X.509 certificate format

  • image

Summary

  • Seen that public key cryptography involves the use of a key part, one of which is public, the other private
  • Considered how an individual’s public key can be used to encrypt messages intended for that individua
  • Discussed how an individual’s private key can be used to assert their identity via a digital signature
  • Explored the details of RSA algorithm and considered its resistance to attack

Leave a comment