I'm reading this article on the basics of cryptography and it says that the main principle is about taking such an algorithm that knowing the end result and the algorithm, an eavesdropper wouldn't be able to determine the initial data.

They give an example:

enter image description here

Supposedly, I know the numbers in the second and third row, but don't know the x and can't derive x. But I can: all I need is to do something like this:

for (int i=0; i<100_000_000; i++)  {
      if (i%7==5)  {    
        if (getPower(i, 3)!=-1)  {
            System.out.println(i+", " + getPower(i, 3));
        }
      }

}

It gives me:

243, 5
177147, 11

meaning, that 243 and 177147 are 3^5 and 3^11 respectively and also give the residual 5 when divided by 7. So it doesn't look like a one-way function to me.

  • 4
    Actually in cryptography you usually only get the third row. Also the numbers are usually significantly larger with thousands of binary digits for the exponent instead of 3. – SEJPM Oct 18 at 10:36
  • 4
    That article claims among other things that signing is the same as encryption. That's a sure sign that you should take everything they have to say on cryptography with heaps of salt. – Maeher Oct 18 at 11:21
  • @Maeher Thank you for the warning. I saw the article being recommended by some user on reddit and decided to give it a try. Could you maybe advise some other more reliable 101-type articles? – Ans Oct 18 at 12:04
  • 5
    There are many things wrong with that article. It still promotes MD4 and MD5 (the article is from 2010!). It says that RSA keys can be swapped (well, it says "can be swopped" , but yeah). That signature verification must be decryption and comparison of the hash value. It explains secret key encryption is insecure, right after explaining a way to establish keys using DH. Algorithms and ciphers are apparently the same thing... Please buy a book instead or follow a course. Books generally get peer reviewed; this one just get rave reviews from other new users probably on style alone. – Maarten Bodewes Oct 18 at 13:45
  • @Maarten Bodewes I'm not a crypto expert and likely won't ever be. I'm just going to set up my first VPS server and it requires the use of SSH, so I wanted to get at least a basic understanding of that public-private key thing. If you could recommend resources that would help me gain it, I would greatly appreciate it. – Ans Oct 18 at 14:06
up vote 3 down vote accepted

So it doesn't look like a one-way function to me.

What you're missing is the scale and basic ideas used in cryptography. Namely the following three facts:

  • Cryptographic exponents for discrete logarithms have thousands of bits instead of 3 as the example in the question. As such merely trying one value at a time, would take several billion years at least.
  • In cryptography, you only ever see the result of the exponentiation after the modular reduction (the third row of the graphic), because there are efficient algorithms for finding logarithms over the real numbers.
  • When using these system in cryptography we don't actually perform $2^{1000}$ or so multiplications but instead use repeated square and multiply which brings this down to a few thousand multiplications. Note that this algorithms requires full knowledge of the exponent to be applied.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.