Simple Introduction to Public-Key Cryptography and Cryptanalysis: Illustration with Random Permutations

In this article, I illustrate the concept of asymmetric key with a simple example. Rather than discussing algorithms such as RSA, (still widely used, for instance to set up a secure website) I focus on a system easier to understand, based on random permutations. I discuss how to generate these random permutations and compound them, and how to enhance such a system, using steganography techniques. I also explain why permutation-based cryptography is not good for public key encryption. In particular, I show how such as system can be reverse-engineered, no matter how sophisticated it is, using cryptanalysis methods. This article also features some nontrivial, interesting asymptotic properties of permutations (usually no taught in math classes) as well as the connection with a specific kind of matrices, yet using simple English rather than advanced math, so that this article can be understood by a wide audience.

Content of the article:

1. Description of my public key encryption system

• Blurring the message (steganography)
• Actual encryption step
• Public and private key
• Decryption step

2. About the random permutations

• Permutation algebra: basics
• Main asymptotic result
• Random permutations

3. Reverse-engineering the system: cryptanalysis

Read the full article here.