Invention –Asymmetric Key Cryptography
The main idea on the development of Asymmetric Key Cryptography, was to avoid two problems, key distribution and digital signatures. Although it was first discovered by M. J. Williamson who worked under GCHQ, his work was kept secret. Few years later, it was first published by W. Diffie and M. Hellman (and R. Merkle) in article “New Directions in Cryptography”, in 1976.
Differences Between Symmetric & Asymmetric Key Cryptography
We may consider Cryptography with two subsections, Public (a.k.a Asymmetric) Key Cryptography, e.g. RSA and Private (a.k.a Symmetric) Key Cryptography, e.g. Block Cipher and Stream Cipher. Let’s compare Symmetric & Asymmetric Key Cryptography in 5-features :
- Key (used enc. & dec.): As the name suggest, in Symmetric Key Cryptography, same key is used for both encryption and decryption. Differently, in Asymmetric Key Cryptography, there are two distinct keys such that; one is used for encryption and another one is used for decryption. Moreover, since key distribution is important for Symmetric Key Cryptography, it is trivial for Asymmetric Key Cryptography.
- Speed (of enc. & dec.): Since key difference yields more computation, Symmetric Key Cryptography processes are faster than Asymmetric Key Cryptography.
- Size (of ciphertext): While, encryption with Symmetric Key Cryptography usually yields same as or less than plaintext size; encryption with Asymmetric Key Cryptography yields more than plaintext size.
- Key Exchange: Since, same key is used for enc. & dec. in Symmetric Key Cryptography, its big problem to exchange or agree on a key against intruder(s). However, there is no need for such exchange in Asymmetric Key Cryptography, we will discuss later.
- Usage for Digital Signatures: While, enc. & dec. can’t be used for digital signatures due confidentiality in Symmetric Key Cryptography, enc. & dec. can be used for digital signatures in Asymmetric Key Cryptography.
General Structure of Asymmetric (Public) Key Cryptography
As mentioned above, there is a pair of key, one of which is said public and the other one private. Alice uses one key and Bob uses the other one. It is infeasible to derive the private key from the public key or the ciphertext.
Let’s consider two decryption process from PKC:
For any plaintext “p” and k_i & K_i for private and public key for user “i” respectively, Dec_1[k_Bob, Enc_1(K_Bob, p)] = p , => only Bob can decrypt with his keys, that yields confidentiality. Dec_2[K_Alice, Enc_2(k_Alice, p)] = p, => anybody can decrypt, yet, only Alice can encrypt, that yields integrity (authentication).
Trapdoor / One Way Function
y=f(x) is easy; x=f(inverse)(y) is infeasible => One-Way Function
y = f_k(x) easy, if k and x are known ;
x = f_k(inverse)(y) easy, if k and y are known — infeasible, if y known but k unknown => Trapdoor
Conclusion –Asymmetric Cipher
- It is computationally easy for any user “i” to generate the key pair (k_i, K_i).
- It is computationally infeasible for Eve to derive k_i from K_i.
- It is computationally infeasible for Eve to derive plaintext from K_i and Ciphertext.
- Key order is optional, can be both order: p = Dec[K_i, Enc(k_i, p)] = Dec[k_i, Enc(K_i, p)]
O.S. Tapsin
Resources: https://d3c33hcgiwev3.cloudfront.net/_2837d90f3b028d98400906a5cc64b497_slides_asymmetric_crypto_overview.pdf?Expires=1568592000&Signature=ShtIGWTs-6h8B9-yAMZXihwxxBpbNEw0ZqPocV-rItGYnhTjbjoa8~zroO5Emw1AYsSS0pSXY2myjjHOlyiwcPgoVIaibl8rUCKrbd0prXZ-1c32jhkzhxTXjBIfmaaaj-v5Mogoa4JNGqV03iQqFOfSJ2WFP-Wq~tF-CPqiFIA_&Key-Pair-Id=APKAJLTNE6QMUY6HBC5A by Sang-Yoon Chang, Ph.D. — https://pdfs.semanticscholar.org/d139/89613117ab2cfcf25bb0bfbb94dc71360bad.pdf — https://ssd.eff.org/en/module/deep-dive-end-end-encryption-how-do-public-key-encryption-systems-work —
|Crypto-Quantus> 