ATSIAP Challenge

RSA Encryption

The first three weeks' ciphers use the same key for encryption and decryption; thus, those are called symmetric ciphers. Before establishing a secure communication channel, the parties need to share the secret key, and this can be tricky - if an attacker eavesdrops and steals the key, then the communication is no longer secure.

To protect against the above scenario, scientists have developed another type of ciphers - asymmetric ciphers. It is asymmetric because each party in the communication has two keys, one is used for encryption, and the other is used for decryption. More specifically, each party has a public key, which is used for encryption and can be shared with everyone, including adversarial attackers. Each party also has a private key (also called secret key), which is used for decryption and should not be shared with anybody. This kind of method is also called public-key encryption.

The general procedure of asymmetric encryption goes as follows: Assuming that Alice wants to send a message to Bob, (1) first, each of them needs to generate a public key and a private key. We name Alice's public key PUa; her private key is PRa. Bob's public key is PUb, and his private key is PRb. (2) Next, the communicating parties need to share their public keys. So Alice sends her public key PUa to Bob, and Bob sends his public key PUb to Alice. (3) When Alice wants to send a secret message (denoted by M) to Bob, she encrypts the message using Bob's public key PUb and obtains a ciphertext C. This process is denoted by Enc(M,Pub) = C. (4) Alice then sends the ciphertext C to Bob. (5) When Bob receives the ciphertext, he can decrypt it using his own private key PRb and obtain the original message M. This process is denoted by Dec(C,PRb) = M. The entire procedure is visualised in the figure below. Conversely, if Bob wants to send a message to Alice, he will encrypt the message using Alice's public key PUa and then the ciphertext across. Then Alice will decrypt the ciphertext using her private key PRa. We omit this part in the figure. In this method, even if an attacker intercepts all the communication and obtains the public keys and the ciphertext, without the private keys, it is impossible to decrypt the ciphertext.

But how come we can encrypt the message with a key and decrypt it with a different key? Well, now we need a little mathematics. There are numerous methods in this scheme; we will use the perhaps most famous one: the RSA public-key cipher. This method was developed by the mathematicians Ron Rivest, Adi Shamir and Leonard Adleman in 1977. (1) First, to generate the public key and the private key, we will need to choose two prime numbers, p and q. Recap: a prime number is a natural number that is greater than 1 and is not a product of any two smaller numbers. Let n = p * q. (2) By convention, we define phi(n) = (p-1)*(q-1). Then we need to choose another prime number e such that 1 < e < phi(n). (3) Next, we find a number d such that (e * d) mod phi(n) = 1 mod phi(n). Here, mod stands for the modulo operator. That is, x mod y returns the remainder of x / y. Once we have found p, q, e and d, we can generate the public key as the pair of (n,e), and the private key as (n,d).

To encrypt a message M, which we assume is a number, we simply compute the following: Enc(M,(n,e)) = M^e mod n = C, where M^e means M raised to the power of e. To decrypt a ciphertext C, we compute the following: Dec(C,(n,d)) = C^d mod n = M.

For example, let us pick p = 3 and q = 11. Then n = p * q = 33. We then choose e = 3, and find d = 7. You can check that (e * d) mod phi(n) = 1 mod phi(n), that is, 21 mod 20 = 1 mod 20. Therefore, the public key is (33,3), and the private key is (33,7). Say the message M is the number 4. The encryption goes Enc(4,(33,3)) = 4^3 mod 33 = 31. So 31 is our ciphertext. To decrypt 31, we compute Dec(31,(33,7)) = 31^7 mod 33 = 4, and we obtain the original message!

Tasks

These days, you can go into a fruit shop and everything looks beautiful. But when you taste the food, the apples or the oranges… Hello! They’ve got no flavour. They’ve been early– forced ripened, right? So, that’s an artificial way. Aboriginals didn’t have the luxury of refrigeration or anything like that. Well, they didn’t need it. So, they had to abide by the rules and regulations of Mother Nature again. She would tell us. For example: fish. I know great fish areas on the eastern seaboard of Australia. I clearly remember when I was, again, a young lad that whenever I saw a lot… and they’re always in single file too. They’re not two or three here. They’re always in single file: brown hairy caterpillars. I knew, through the training down the line, I knew that the sea mullet were on the way traveling up from… because the first time we’d hear of those sea mullets, they’d net thousands of cases down in Newcastle. Newcastle was a notorious place for the sea mullet. They must have come in close there and we knew then. It was only a matter of weeks before the sea mullets would come back up our way and that’s a classic example from Mother Nature. With regard to another one growing up. We had these trees planted over the Broadbeach burial ground… was the wudjuru tree, that’s the eucalyptus tree (edit note – not eucalyptus), tea tree and that was an important medical addition to the family chemist, our chemist shop. When the flowers came on with the wudjuru tree, you knew for sure, when those little creamy flowers came on, you said, “Hello, big moogerah on the way.” What’s that? Rain. Rain’s on the way. And sure enough, it doesn’t matter what the weather bureau says. I remember when Pacific Fair was just starting up, just been built, the old Pacific Fair. I remember this, because I told my beautiful mother. I was riding down, I had a push bike or something and I was riding down there and when I got home I said to my mother, “Holy heck. We’re in for big rain.” And my mother said, Teresa, she said, “How do you know?” What would I know? And I said, “Because the tea tree, wudjuru trees in the median strip on the way to Pacific Fair… they’re loaded with flowers.” Full of nectar, good for native bees, Mac. I said, “Loaded with flowers” and the weather bureau-how’s this? The weather bureau at the time said no rain on the way, blue skies etc., etc.. But, you know what? Down she came. And this was around ’53, 1953 or 1963. Let the records clearly show that the Gold Coast was flooded out. Mother Nature was right and the weather bureau with all their technology, they missed the mark.

Consider the following parameters: p = 7, q = 13, e = 41 and d = 65. Encrypt the year of the flood. The result is in the link of the next task. Note that the maximum message you can encrypt is less than n, which is 91 in this case.

Welcome to the ATSIAP Year 7-9 Challenge on Cybersecurity (Week 5)

RSA Encryption

Tasks

Official Sponsors

Previous Tasks

Contact Us