Jump to content

SkySurveyBanner.jpg.21855908fce40597655603b6c9af720d.jpg

A maths question about encription


Recommended Posts

We don’t seem to have a maths section so I’ll post this here …

Just out of interest I tried to understand encryption and decryption used on the internet. I think I understand the basic principles of the use of public and private keys. I have also followed some YouTube tutorials explaining the basic principles (using low numbers) of how primes are used to create the algorithms for the creation of public and private keys. The RSA method. So far so good.

OK I understand that exact decryption is phenomenally difficult without the private key. However, there is something I am confused about. In all the simple explanations I have seen, each character in the original message is encrypted to a particular character or (in fact) number.  Since everyone has access to the public key, everyone knows what that mapping is. So what is to stop someone who intercepts the encrypted  message from using statistical methods  to at least having a stab at decrypting alphabetical text?

Presumably I am simply wrong. In other words there must be something else done that prevents the message being partially decrypted in this way. 

Link to comment
Share on other sites

4 hours ago, AngryDonkey said:

With RSA, text is typically encrypted in blocks and not letter by letter to prevent this.

By that do you mean each block is encrypted and decrypted with a different public and private key?  I can see how that would work. 

Link to comment
Share on other sites

8 hours ago, Ouroboros said:

So what is to stop someone who intercepts the encrypted  message from using statistical methods

Statistical methods are generally used to decrypt cyphers. A good read on the use of statistics through the history of code breaking is "Code Breakers" by David Kahn.

What you are describing, I believe, is a brute force attack. This is very time consuming for longer messages. With todays computers it is starting to become doable, but that's also why new methods and longer keys are constantly being developed.

  • Like 1
Link to comment
Share on other sites

9 hours ago, Ouroboros said:

However, there is something I am confused about. In all the simple explanations I have seen, each character in the original message is encrypted to a particular character or (in fact) number.  Since everyone has access to the public key, everyone knows what that mapping is.

That is the thing with RSA type encryption - that is not how it works.

What you are describing is symmetrical cypher.

With RSA type encryption we have asymmetrical mapping. Simplest explanation would be as follows - imagine you have function that says

a mod b = output value

(reminder or modulo function)

if you have output value of say 5 and you know that b is 10 - then you can't tell if a is 5 or 15 or 25 or 35 and so on ...

In fact - if you look at RSA encoding function - it uses modulo:

image.png.a5532737af2aaad22c36750ec3c9f6c8.png

 

Link to comment
Share on other sites

Yep, I get all that @vlaiv.  But can’t an interceptor of the encrypted message use the public key to encrypt plain text test messages of his own to see what the public key does to each character?  I’m sure your answer is going to be that even if he does that he doesn’t have enough information to even have a stab at decrypting the original message. I think that’s the conceptual block I’m having. I can’t see why a message encrypted using the RSA method isn’t at least partially susceptible to decryption in the way I describe.  Sorry if I’m being a bit thick! :) 

Link to comment
Share on other sites

12 hours ago, AngryDonkey said:

A public key system is not very efficient in encryting long messages and usually a hybrid system is used which uses both a public as well as a symetric key. There is a good description here: https://en.wikipedia.org/wiki/Hybrid_cryptosystem

Thank you I will read this and try and get my head around it.

I started all this after trying to understand how quantum computing works and why it is a threat to current encryption.   I then realised I didn’t even understand  current encryption methods, except in the most hand waving terms, and thought I ought to remedy that first. :) 

Link to comment
Share on other sites

3 hours ago, Ouroboros said:

Yep, I get all that @vlaiv.  But can’t an interceptor of the encrypted message use the public key to encrypt plain text test messages of his own to see what the public key does to each character?  I’m sure your answer is going to be that even if he does that he doesn’t have enough information to even have a stab at decrypting the original message. I think that’s the conceptual block I’m having. I can’t see why a message encrypted using the RSA method isn’t at least partially susceptible to decryption in the way I describe.  Sorry if I’m being a bit thick! :) 

Sure that attacker can take any plain text and encrypt it. There is no mystery in how encryption part works - that is not the strength of RSA algorithm.

If you have public key - you also have private key as well. Attacker does not even have to bother seeing what happens during encryption - they already have private key in their hands, all they need to do is to compute it.

It is far easier just to compute private key from public then it would be to somehow "decipher" encryption stats with plaintext and public keys.

Strength of RSA algorithm lies in the fact that it is very computationally expensive to find private key from public key. It is fast to generate both public and private keys from base prime numbers but it is very very difficult to go in reverse direction from public key to base prime number in order to derive private key part.

Here is an example. If I say - what is 11 x 17 - you should be able to do it in your head in no time - 11 x 10 + 11 x 7 = 110 + 77 = 187, but if I asked you - what two numbers you have to multiply to get 187, how much time would it take to figure out it is 11 and 17 and how would you go about it?

That is the strength of RSA - some mathematical procedures are far far easier to do in "forward" direction than it is in "reverse".  That will be true until we find efficient factoring algorithm that can do it in less time.

Problem is much much greater in general and is one that you can easily win $1,000,000.00 if you solve it :D

It is one of millennial prizes - so called "P vs NP"

We still don't know or have proof if P=NP or P!=NP.

P and NP stand for "polynomial time" and NP stands for "nondeterministic polynomial" time. Two terms are used to denote complexity of a problem (or algorithm as a solution).

P means that complexity is polynomial in nature - and can be thought of - for input of size N, output is calculate in time that is equal to P(N) - or polynomial of N. That polynomial can be as simple as 2X or can be more complex as X^5+4*X^2, but in both cases if you double the amount of input data - it would take in first case x4 more time to solve it and in second case something like ~x40 more time to solve it. Both are within reach of either waiting some time or using more machines in parallel or simply waiting for computers to become stronger - and it will be solved.

NP class of problems have "stronger" complexity where complexity is not polynomial but rather exponential for example (don't nondeterministic polynomial part confuse you - it is conceptual machine that does calculations - that is where term comes from).

If we increase input size - time to calculate output is increased much much more than it would be in P case.

This is why say 2048 bit RSA key is significantly stronger than 1024 bit key. We just doubled amount of input data - but time to factor that large number increased much much more.

Back to P vs NP - we still don't know following: if problem has solution that is NP in nature (algorithm has nondeterministic polynomial complexity) - is there solution to the same problem that is P in the nature, and that holds always (P=NP case) or if problem is NP then there certainly is no P solution to it (P!=NP).

One who solves this and provides proof can win one million dollars prize

(https://en.wikipedia.org/wiki/Millennium_Prize_Problems)

 

Link to comment
Share on other sites

Thank you, @vlaiv, for your lengthy answer. I knew most of that, at least in general terms, and I have no conceptual problem with it. I don’t think it addressed the question I am asking. Maybe that’s down to my limited ability to explain it. 

Link to comment
Share on other sites

10 hours ago, Ouroboros said:

But can’t an interceptor of the encrypted message use the public key to encrypt plain text test messages of his own to see what the public key does to each character?

You don't need to do that - that part is very well known. You won't get any information if you perform that task on your plain text, at least not any sort of particularly important information

Check out https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Encryption

Cypher text is just message encoded as integer raised to some power (depending on public key), module some other number (again part of public key).

  • Like 1
Link to comment
Share on other sites

@Ouroboros

Ok, I finally think I understand I think that I finally understand what has been bugging you.

With RSA encryption - you don't encrypt message in blocks like with symmetric ciphers - you encrypt message as a whole.

It would be easy to break the message if one would for example encrypt every byte on its own. That would give us 256 combination as each byte would always map to same number and we could then use statistical means to figure out which output number corresponds to which plain text byte - but that is not how RSA works - it encrypts whole message, and if message is short - is being padded to be of appropriate length - to create large enough whole number to be encrypted.

 

Edited by vlaiv
  • Like 1
Link to comment
Share on other sites

Yes, OK. I think I had in mind that plain text character “A” would be encrypted to such and such and “B” to something else …. and so on then it wouldn’t be a very good encryption method. 

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue. By using this site, you agree to our Terms of Use.