dlp

Programs solving the discrete logarithm problem.

Problem statement: find value a such that g^a mod p = A

a is 31 bit unsigned integer; g, p and A are specified in a .conf file, in hex format like this:

g=A4D1CBD5C3FD34126765A442EFB99905F8104DD258AC507FD6406CFF14266D31266FEA1E5C41564B777E690F5504F213160217B4B01B886A5E91547F9E2749F4D7FBD7D3B9A92EE1909D0D2263F80A76A6A24C087A091F531DBF0A0169B6A28AD662A4D18E73AFA32D779D5918D08BC8858F4DCEF97C2A24855E6EEB22B3B2E5
p=B10B8F96A080E01DDE92DE5EAE5D54EC52C99FBCFB06A3C69A6A9DCA52D23B616073E28675A23D189838EF1E2EE652C013ECB4AEA906112324975C3CD49B83BFACCBDD7D90C4BD7098488E9C219A73724EFFD6FAE5644738FAA31A4FF55BCCC0A151AF5F0DC8B4BD45BF37DF365C1A65E68CFDA76D4DA708DF1FB2BC2E4A4371
A=4FB7FC5543219711B7144FDA72E4A25DDCBC79DB02D51C742602FB3D0D40E04C46CD22EC33B43DBEB5C05217A9135904DD8B7915335C9337D6CF07464E6E4D762B2C8B3A2F84313D0014C74D4EFE1FB00147B3D8498A755D6E2E6729A13B0F086BFEAB83E37B6401FEA9884AC1E493D7F91A065CD25E22EE5A66433F8C308DED

Motivation

I used this code to decrypt a Diffie-Hellman key exchange between mobile app and "smart" device. The mobile app is Air Matters and the device is Philips Air Purifier AC2729. I figured out through reverse engineering that the random exponent generated by the app is only 31 bits. My first tries to crack this was using naive brute force but then I found the Baby-step Giant-step algorithm which runs in O(sqrt(N)) time and when N is only 2^31, it finds solution for less than a second on a modern PC.

Build

apt-get install libssl-dev
./build.sh

Run

There are brute force implementations in Java and C. Those can be tuned with the start and threads parameters in the conf file to specify the starting value and the number of threads being used. Run them with:

java -cp bin dlp.DLP dlp.conf

or:

bin/dlpc dlp.conf

On my machine (Intel Xeon CPU E5-1620 @ 3.50GHz) with 8 cores the Java version takes 24min to find solution for the parameters in the sample conf file. The C version is two times faster -- it takes about 12min.

If you run the Java version with --fast it will use the Baby-step Giant-step which solves the problem instantly:

$ java -cp bin dlp.DLP --fast dlp.conf
g=a4d1cbd5c3fd34126765a442efb99905f8104dd258ac507fd6406cff14266d31266fea1e5c41564b777e690f5504f213160217b4b01b886a5e91547f9e2749f4d7fbd7d3b9a92ee1909d0d2263f80a76a6a24c087a091f531dbf0a0169b6a28ad662a4d18e73afa32d779d5918d08bc8858f4dcef97c2a24855e6eeb22b3b2e5
p=b10b8f96a080e01dde92de5eae5d54ec52c99fbcfb06a3c69a6a9dca52d23b616073e28675a23d189838ef1e2ee652c013ecb4aea906112324975c3cd49b83bfaccbdd7d90c4bd7098488e9c219a73724effd6fae5644738faa31a4ff55bccc0a151af5f0dc8b4bd45bf37df365c1a65e68cfda76d4da708df1fb2bc2e4a4371
A=4fb7fc5543219711b7144fda72e4a25ddcbc79db02d51c742602fb3d0d40e04c46cd22ec33b43dbeb5c05217a9135904dd8b7915335c9337d6cf07464e6e4d762b2c8b3a2f84313d0014c74d4efe1fb00147b3d8498a755d6e2e6729a13b0f086bfeab83e37b6401fea9884ac1e493d7f91a065cd25e22ee5a66433f8c308ded

Solving g^a mod p = A using Baby-step Giant-step algorithm

solution found, a=1988873156