本次澳洲代写主要为C语言加密解密算法相关

COMP10002 Foundations of Algorithms Awesome
Semester 1, 2021
Assignment 1: The DUHK Attack

Change Log
Version 1.1
• Typo: Capitalized some references where they were erroneously lowercase
• Typo: End of Section 4.1, “one call AES” → “one called AES”.
• Typo: End of Section 4.3, “0xC.”→ “0xCC” since 204 in base ten is 0xCC.
• Typo: Locations that used the command ./assignment1 have been changed to use ./program1
• Clarification: You do not need to read the research paper for this assignment, it is present only for enrichment
and enjoyment. It also will not make the assignment easier if you do read it.
• Correction: Section 8, We did not previously provide sample output for the two input files. The latest version of
the package contains two additional test files and two matching output files, the same ones used for Grok.

1 Learning Outcomes
In this assignment you will demonstrate your abilities functions, pointers, arrays, loops, and conditionals. The as-
signment covers the following components of the textbook: Chapters 1 to 7 inclusive, along with material from pages
230-235.
The assignment is intended to be very challenging and push your programming skills significantly further than Grok,
as well as testing your algorithmic thinking. However, it is also intended to be fun, and a very close analogue to a real
world task. The first time I coded the full version of the attack for the research paper took me a long time! You can
anticipate that this assignment might also take quite a while, but the payoff will be in your new skills and learning.
The inspiration for this assignment is the research paper “Practical state recovery attacks against legacy RNG imple-
mentations” by Shaanan N. Cohney, Matthew D. Green, and Nadia Heninger, with more details at duhkattack.com.
Read all the instructions carefully and make sure you understand what is expected of you
2 Full Story (just for fun)
Watch the video here and read the accompanying description!
3 The (Short) Story
You have intercepted an encrypted message, and know some details about how
it was generated. The message was produced by taking the xor of the original
message with some key k1.
This key, k1, was produced using a pseudorandom number generator at times T11
to T19.
However, while you know all the times at which the generator was ever used (T0
to T19), you only have access to outputs from T9 and T10 (O9 and O10).
You reverse engineered the generator and found it used a second key, k2.
Your goal is to reconstruct k1, and use it to decrypt the original message.
a
aWhen you succeed, you might notice missing punctuation in the message—we suspect the senders
were just saving a few characters 😉
4 Background Material
The following additional material provides context for the assignment itself. You can also watch the videos uploaded to
the LMS for a walkthrough of the assignment and the background material.

4.1 Generating Random Numbers
Computers don’t know how to be truly random. While one can purchase a device to measure very unpredictable phe-
nomena (like radioactive decays) and convert them into random numbers, most computers have no such hardware.
Instead, computers rely on algorithms that produce random looking output that is very hard for an outsider to distin-
guish from output that is truly random. How hard? We say that no algorithm that runs in polynomial time (Big O of
any polynomial) should be able to tell if the output is truly random or not with anymore than an minute probability.
We call these pseudorandom number generators.
Importantly, the sequence of random numbers should also not be guessable. If you see prior output from the algorithm,
they should be so “random” that you can’t guess what will come next. This is important because we typically use a
random generator to make random keys for encryption.
One well known algorithm to generate random numbers is the the following pseudorandom number generator (known
as the ‘ANSI X9.31 DRBG’).
The generator itself relies on having a cryptographic function, normally one called AES that we discuss in a bit more
detail in Section 4.5. Because of this choice, our assignment will process 128-bits at a time, the same amount as AES.We
represent the encryption of message m under AES with k key as AESk(m) = c.