search

Varad0612 / The-McEliece-Cryptosystem

This is the C implementation of the McEliece Cryptosystem based on QC-MDPC codes.
22 stars 10 forks source link

Cannot find inverse? #1

Open vanrein opened 5 years ago

vanrein commented 5 years ago

I'm playing with your code, and it's repeatedly returning a failure,

mceliece.git# ./keygen 
Enter n0: 2
Enter p: 4800
Enter w: 90
Enter t: 84
Input seed or -1 to use default seed: -1
MDPC code generated....
Time for H: 1.600155
Time for H: 1.462856
Construction of G started...
Could not find inverse, exiting...

It's not clear what I should do to fix this. Is this a code thing, or a McEliece thing?

In general: McEliece is new to me, as to many others. I also didn't understand inhowfar run, init, keygen overlap. Could you briefly comment on that in the README, and perhaps add a gentle introduction that you'd advise?

I'm a cryptographer, and feel a desire to get on board, and stepping stones like this form a useful playground to get a feel. Excellent idea to post an implementation to play around with!

Varad0612 commented 5 years ago

Hi,

I'll take a look at it today and see why the inverse computation is failing. In the mean time, feel free to play with the code to see how the system works.

Regards, Varad

On Saturday, March 30, 2019, vanrein notifications@github.com wrote:

I'm playing with your code, and it's repeatedly returning a failure,

mceliece.git# ./keygen Enter n0: 2 Enter p: 4800 Enter w: 90 Enter t: 84 Input seed or -1 to use default seed: -1 MDPC code generated.... Time for H: 1.600155 Time for H: 1.462856 Construction of G started... Could not find inverse, exiting...

It's not clear what I should do to fix this. Is this a code thing, or a McEliece thing?

In general: McEliece is new to me, as to many others. I also didn't understand inhowfar run, init, keygen overlap. Could you briefly comment on that in the README, and perhaps add a gentle introduction that you'd advise?

I'm a cryptographer, and feel a desire to get on board, and stepping stones like this form a useful playground to get a feel. Excellent idea to post an implementation to play around with!

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Varad0612/The-McEliece-Cryptosystem/issues/1, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtri9oVJ5syi01Nd7wQlml_MUYV_6CVks5vbyTtgaJpZM4cToNi .

Varad0612 commented 5 years ago

Hi, I ran the ./keygen program and was able to generate the keys successfully. Since the parity check matrix is generated by randomly setting bits in the first row and then constructing the complete matrix by circular rotation of the rows, it might be possible that you ran into an unlucky corner case where the n0-1 circular matrix did not have an inverse. I will add a check condition in order to make sure that this matrix has an inverse before proceeding. Thanks for bringing it to my attention!

In the mean time, you can try running the program with smaller inputs as mentioned in the README so that you don't have to wait for the long computations.

Regards, Varad

On Sat, Mar 30, 2019 at 10:05 AM Varad Deshpande varad0612@gmail.com wrote:

Hi,

I'll take a look at it today and see why the inverse computation is failing. In the mean time, feel free to play with the code to see how the system works.

Regards, Varad

On Saturday, March 30, 2019, vanrein notifications@github.com wrote:

I'm playing with your code, and it's repeatedly returning a failure,

mceliece.git# ./keygen Enter n0: 2 Enter p: 4800 Enter w: 90 Enter t: 84 Input seed or -1 to use default seed: -1 MDPC code generated.... Time for H: 1.600155 Time for H: 1.462856 Construction of G started... Could not find inverse, exiting...

It's not clear what I should do to fix this. Is this a code thing, or a McEliece thing?

In general: McEliece is new to me, as to many others. I also didn't understand inhowfar run, init, keygen overlap. Could you briefly comment on that in the README, and perhaps add a gentle introduction that you'd advise?

I'm a cryptographer, and feel a desire to get on board, and stepping stones like this form a useful playground to get a feel. Excellent idea to post an implementation to play around with!

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/Varad0612/The-McEliece-Cryptosystem/issues/1, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtri9oVJ5syi01Nd7wQlml_MUYV_6CVks5vbyTtgaJpZM4cToNi .

vanrein commented 5 years ago

Hey Varad,

Thanks! I had tried a few runs, but those were after the same build (and run? init? I'm not sure.)

After your comments, I started completely from scratch, and did indeed get through.

It's now encrypting. Gosh, that too takes (almost) forever. Incredible. I new the keys would be MB-ish, but not that even encrypt and decrypt would take so long.

As said before, it'd be really helpful to understand what the phases mean (even if just by referencing a source elsewhere). It feels like I'm doing things that overlap, such as keygen (or paramgen).

-Rick

vanrein commented 5 years ago

Also,

I had to enter w and t in the other order than in the README, but assume that's as intended.

I got to decrypt, but was struck by "Enter code of length 4800:" which I didn't know how to answer... an attempt with <Encryption.txt caused a segfault.

(Just sharing experiences, not meant as complaints or anything.)

-Rick

Varad0612 commented 5 years ago

Hi Rick,

The most time consuming step in the entire process is finding the inverse of a large matrix. I believe that this process can be substantially made faster if its implemented using multi threading. If you want to test out the encryption and decryption, you can run the test file. It has some default parameters and message values that it encrypts and decrypts. Another thing you can do is all the user to enter a message of any length and then modify the code to add padding to the input message to make it of length 'k'. You definitely do not have to do keygen every time.

This is a very vanilla implementation of the the cryptosystem and there is a lot of room for making it more efficient. So, feel free to modify the code to suit your needs. I have attached a paper below that will give you a good idea of how the QC-MDPC based McEliece cryptosystem works. Have fun!

Regards, Varad

On Sat, Mar 30, 2019 at 5:42 PM vanrein notifications@github.com wrote:

Also,

I had to enter w and t in the other order than in the README, but assume that's as intended.

I got to decrypt, but was struck by "Enter code of length 4800:" which I didn't know how to answer... an attempt with <Encryption.txt caused a segfault.

(Just sharing experiences, not meant as complaints or anything.)

-Rick

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/Varad0612/The-McEliece-Cryptosystem/issues/1#issuecomment-478291726, or mute the thread https://github.com/notifications/unsubscribe-auth/AJtri-uMGClC2yKdNkl03YmfwN2oP1DSks5vb9pTgaJpZM4cToNi .