CODEWITHSUNDEEP
javamd5
Habitat
Habitat

Reputation: 709

Generate an MD5 hash with six leading zeros

Doing some practice coding problems in Java from Advent of Code and came across one where it asked me to find the smallest six-digit integer, combined with the leading string of iwrupvqb, that produced an MD5 hash that started with five zeros.

I found the answer to this part using the Apache DigestUtils.md5Hex function where I just brute forced through 100000-999999 and combined it with iwrupvqbuntil I got an MD5 that started with five zeros.

The answer came out to be iwrupvqb346386 creating the hash:

0000045c5e2b3911eb937d9d8c574f09

Now it's asking me to find one with six leading zeros. I've been going through pages and pages of how the md5 algorithm works, inverting MD5, etc but can't seem to figure out the problem in an equation format that would help me determine how the MD5 would be calculated based on the characters used.

I even let this loop run for like 30 mins - an hour to see if it got any hits outside of a six digit integer (because apparently there are none combined with this text phrase that create six leading zeros)

I don't really know anything about hexadecimal so at this point I'm just taking shots in the dark and trying to guess number combos all night isn't really my thing. I don't necessarily need to solve this problem for anything besides practice but I am curious to know more about what's going on here. (And yes I am aware that MD5 is compromised and I wouldn't ever use it in production)

Upvotes: 3

Views: 2991

Answers (2)

RonDBA
RonDBA

Reputation: 86

I'm also working through the Advent of Code but I'm using PowerShell. I solved Puzzle 2 of Day 4 with basically the same code that I used to solve Puzzle 1. The only change was to the WHILE condition to check for six leading zeroes. It did take a lot longer to run than it did to solve for Puzzle 1. I just kicked it off and went to bed after I saw this post. Got my answer when I woke up. My code is posted at Github. Advent of Code Day 4 Puzzle 2 solution with PowerShell

Upvotes: 0

Thilo
Thilo

Reputation: 262774

This problem can only be solved by brute-forcing. That is exactly how "proof-of-work" in Bitcoin works, for example. The only way to speed it up is to optimize each step in your calculation. Bitcoin miners have moved to specialized hardware because of this. They don't do anything "special" or "clever", they just calculate hashes very, very fast.

You can only optimize the code and throw more/better hardware at it. A cluster of compute nodes would also work well here, the problem lends itself to parallel processing (again, Bitcoin mining pools).

If you have a multi-core CPU, an easy thing to do is to use one Thread per CPU. Should speed up linearly (which may still not be fast enough).

Upvotes: 3

Related Questions