代写Birthday Paradox Attack调试Python程序

日期：2025-11-08 06:41

Question 1 – The Birthday Paradox Attack [50%]

This exercise illustrates the birthday paradox in the context of hash collisions, using a simple toy “hash” function based on bitwise XOR. You will write a Python program to demonstrate how collisions can occur much more easily than intuition may suggest.

Instructions

Write a Python program that performs the following steps:

1.   Generate XOR “hashes” for prime sets.

o  Randomly generate 16 sets of three distinct prime numbers, all less than 256 (28).

o  Compute the hash of each set by taking the bitwise XOR of the three integers:

Store these 16 hash values as your reference set.

2.   Search for a matching composite set.

o  Repeatedly generate random sets of three distinct composite numbers less than 256.

o  Compute the XOR hash for each composite set and compare it to the 16 prime-set hashes in your reference set.

o  Stop as soon as you find a composite set whose hash matches one of the prime-set hashes in your reference set.

3.   Output and submission format.

o  Your submitted Python file must include, as commented output at the end of the file:

The 16 prime sets and their XOR hashes.

The matching composite set (if found) and its hash.

The total number of composite sets tested before a match occurred.

The random seed used (e.g., random.seed(2025)).

o  If no match was found within a reasonable number of attempts, state that clearly.

o  Do not submit screenshots; include all output and explanations as comments within your .py file.

4.   Conceptual check.

o  Briefly note in comments how this toy example relates to the birthday paradox; that is, why collisions become likely once the number of

generated hashes approaches roughly the square root of the hash space size.

Additional Requirements

•     Each “set” must be an unordered collection of three distinct numbers (no

repetitions). For example, {5, 11, 5} is invalid, and  {2, 7, 19} is the same as {19, 2, 7}.

•     Use a fixed random seed to ensure reproducibility.

•     The XOR hash should be computed directly using Python’s bitwise XOR operator (^).

•     Keep your code well commented and clear.

Expected Results

Because XOR outputs very small integer values (only a few bits when numbers < 28), collisions should appear quickly—often after testing only a few dozen composite sets.

This models the birthday paradox: the probability of two values colliding rises sharply once you generate roughly √N distinct hashes, where Nis the number of possible outputs.

Question 2 – Attempting a Birthday Attack on SHA-256 [50%]

This question extends Question 1 (The Birthday Paradox Attack) by replacing the simple XOR operation with a cryptographically secure hash function (SHA-256). The goal is to empirically  show  how  unlikely  it  is  to  find  a  hash  collision  when  using  a  modern cryptographic hash function.

Instructions

Write  a  Python  program  using  the  cryptography library  (see  the  documentation  at https://cryptography.io/en/latest/hazmat/primitives/cryptographic-hashes.html)            that performs the following experiment:

1.   Generate SHA-256 digests of prime sets.

o  Randomly generate 16 sets of three distinct prime numbers, all less than 256.

o  For each set {p1, p2, p3}, compute the SHA-256 digest of the concatenation of their ASCII decimal representations (e.g., b"251", b"157", b"191").

o  Store these 16 hash values as your reference digests.

2.   Generate SHA-256 digests of composite sets.

o  Generate 1,000 sets of three distinct composite numbers, all less than 256.

o  Compute their SHA-256 digests in exactly the same format as in Step 1.

o  For each composite digest, check whether it matches any of the 16 prime digests. Stop early if a collision is found.

3.   Output and submission format.

o  Your  submitted Python code must include the following as commented output at the end of the file:

The 16 prime sets of your reference set (and their corresponding digests).

Up to 10 composite attempts (with their sets and digests).

The final result, clearly stating whether a collision was found or not.

The fixed random seed used (e.g., random.seed(2025)).

o  Do  not submit screenshots. All results and explanations must appear as comments within your code file.

4.   Explanation (as comments in the code).

o  After your code, include a short 1–3 paragraph explanation (as a comment block) describing:

Why a collision is extremely unlikely with SHA-256.

How this relates to the birthday paradox, specifically that a 256-bit hash requires roughly 2128  attempts on average to find a collision.

Why your  1,000-trial  experiment  will  almost  certainly  yield  no matches.

Additional Requirements

•     Treat each set as an unordered collection of distinct elements (no repetitions, and order does not matter). For example,  {5, 11, 5} is invalid, and {2, 41, 227} is the same as {41, 227, 2}.

•     Use a fixed random seed so results are reproducible.

•     Verify that all composite numbers are indeed non-prime and greater than 1.

•     To avoid accidental false collisions:

o  Do not use bytes(n) directly, as it produces a sequence of null bytes (\x00) that can unintentionally overlap between inputs.

o  Avoid ambiguous string concatenations such as "2" + "41" + "227" and "24" + "12" + "27", which both yield "241227".

o  Instead,      include      delimiters      (e.g.,      b':')      or      use      separate digest.update(b"...") calls.

Expected Results

You          are          not           expected          to          find           a          real           collision. Even if you computed all possible sets of three composite numbers  less than  256,  a  true  collision with  SHA-256  would  still  be  astronomically unlikely, requiring roughly 2128 trials on average. For perspective, generating 1.39 × 106 SHA-256 hashes takes about 40 seconds on the instructor’s laptop, but 2128 hashes would take ≈ 5.9 × 1025 years. This is far longer than the expected lifetime of our galaxy, the Milky Way.

If, after verifying your code, you genuinely find a collision, document it carefully in your output comments, and you will receive full marks for this assignment regardless of other results.