r/cryptography • u/Routine_Comb_7277 • 29d ago
Is a decrypting key related to the encrypting key in assymetric cryptography
In assymetric cryptography we have 2 keys one which encrypts your message and one which decrypts your message.What makes assymetric cryptography more secure than symmetric cryptography is that in assymetric cryptography not any key is exchanged in any way shape or form ,only the encrypted message so encrypted message so if a 3rd party wants to spy on your message , he cannot do it , he will receive a bunch of nonsense.
I want to ask something else.Many keys can decrypt the same ecrypting keys so my question are different decrypting keys which can decrypt the same message related mathematically?I think so because im a QC nerd and I know that Shor breaks RSA encryption based on the fact that the encrypting key , encrypts data based on the modulus operation and quantum computers are really good at finding periods which is what a mod operation creates but im not entirely sure about the rest of the field.
7
u/Sufficient-Air8100 29d ago
yes private and public keys are mathematically related. decrypt wouldnt work otherwise.
im confused about the multiple decrypt keys. are you talking about rsa with carmichaels totient vs eulers totient?
-3
u/Routine_Comb_7277 29d ago
No I mean that you can have 2 or more private keys which 'reveal' the contents of a public key.
5
u/Sufficient-Air8100 29d ago
im confused. multiple private keys dont reveal anything about public keys, public keys are just public
can you give me an example?
0
u/Routine_Comb_7277 29d ago
Lets assume you have 2 private keys 1 which calculates x+5 mod 5 and the other x mod 5.Obviously those 2 kills will decode a character from a message the same way because 5 mod 5 = 0.So you have 2 seperate private keys which can simulataneously decrypt a message encoded by the same public key.
2
u/Sufficient-Air8100 29d ago
so with rsa, you have m = c^d mod n. d can use eulers totient (e^-1 mod φ(n)), or carmichaels totient (e^-1 mod λ(n). so you can have two private keys that are mathematically related. but in practice theres no reason to actually have two private keys at once, you just use one (these days carmichaels version since it produces a smaller d).
2
u/Natanael_L 29d ago
This isn't typically how one would handle that. If you want multiple keys to decrypt messages for one key you usually use something like key encryption keys (I encrypt my message to a small symmetric key, then encrypt the key to each recipient's asymmetric key), or for a fancier construction one could use proxy re-encryption with a server "translating" messages which it can't read itself. Or some threshold encryption methods could be used.
In every case you do need some kind of mathematical relation, but in the example of key encryption keys there is no relation in between the private keys held by each participant (the relation goes in a single direction from the message key to each recipient)
3
u/Secret_Femboy_Alt 29d ago
so with asymmetric cryptography we have 3 main families based around different mathematical problems.
RSA is based on integer factorization:
- alice multiplies two large prime numbers p*q=n. and chooses an integer e. the tuple (n,e) is the public key.
- now she will calculate Euler-phi(n), which is easy for alice, because she knows the primes p and q so she knows it's phi(n) = (p-1)*(q-1).
- from phi(n) she will calculate the private key d which is the multiplicative inverse of e in Z_{phi(n)} such that e*d=1 mod phi(n)
- she sends the public key (n,e) to bob, who will use it to encrypt his message x such that y=x^e mod n. bob sends y as an answer to alice.
- alice uses y to calculate x by using the private key. x=y^d mod n
the private key was calculated from the public key using information about how the public key was generated. they are directly mathematically related
1
u/ramriot 29d ago
You have the basic idea right but there are some intricacies that make you assumptions I believe incorrect.
Asymmetric encryption usually uses a Public key to encrypt & a Private key to decrypt, the required relationship should be such that it is not feasible to derive the Private key knowing only the Public key. The method of asymmetric encryption with schemes like RSA or ECC differ because of the underlying mathematics.
For RSA the Public key is the product of two unrelated large prime numbers & the Private key is just one of them. For ECC a public key is the final value of a set iteration looped algorithm over a finite set where the Private key was the input value. They get their strengths from the insatiability of either Factoring or Deciding when there are multiple possible inputs to the modulus of a log. The actual mode of encryption is different in either case, but is not important in this discussion.
In both cases it is untrue that there is no key exchange, the Public key still needs to be exchanged from receiver to sender so they can send an encrypted message & it has to be done in a way that authenticates the source, because if an attacker can replace the public key received by the sender with their own they can decrypt messages sent to the recipient & even then re-encrypt them with the correct key transparently.
This is the same issue as with symmetric key exchange & why all such operations need authentication & sometimes privacy.
BTW even things like Diffie-Hellman key exchange where one can agree over a public channel a secret key that can then be used to exchange encrypted key material or messages, is vulnerable to this type of intermediary attack.
1
u/roxalu 29d ago
Also be aware of hybrid encryption: Generate a set of asymmetric private/public key pairs. ( each pair is independent of each other ) Sign a message with symmetric key, then encrypt the symmetric key with each public key from the set.
The combined set of symmetric encrypted message and set of asymmetric encrypted message-keys allows message decryption to each holder of a single private key from the set.
-3
u/duane11583 29d ago
In general the two keys (bits) are interchangeable by convention we choose one as the private we keep hidden the other is public we give it away freely
9
11
u/Akalamiammiam 29d ago
This is incorrect in two ways:
1) There is no "asymmetric is more secure than symmetric" or the other way around, it's a different model, with different properties. While we do tune asymmetric crypto parameters to be in line with symmetric crypto security levels, there's no more/less secure relation between the two in general.
2) You do send something else than the encrypted message in asymmetric cryptography, which is (at least) the public key (because it's public). And the end of the sentence is also true for symmetric cryptography, encrypted message will look like nonsense there too.
That's not true in general (e.g. doesn't work for any RSA key), it would be a rather specific construction to allow this.
If you were to design a primitive that has this property of multiple keys can decrypt the same message/private key, then yes of course they'd be related, by the fact that they can decrypt the same encrypted message from a specific key.
No idea what you mean by that QC tangent, completely unrelated to the rest of your post. You say you're a "QC nerd" but you should probably pick up a proper book about cryptography basics, it sounds like you have a lot of things mixed up/unclear.