Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

What is the expected number of trials required to selectively forge ed25519?

Please include how it is calculated.

share|improve this question
1  
There's not an infinite amount of parallel processors. I try dealing with real issues. –  fgrieu Mar 19 at 15:59
    
@fgrieu Thank you for looking fgrieu! Right, that's the best I can understand cryptography, by that example I heard. My question is does that reality extend to maliciously generating valid signatures? My intuition says yes because of the nature of cryptography, but I'd like to be certain because I can barely comprehend this field. Thank you so much in advance for any explanation you can give! –  Gracchus Mar 19 at 16:12
    
Your intuition is right. In cryptography, we assume a malicious adversary. When dealing with signatures, we assume the adversary is trying hard (including with a plausible number of parallel processors) to forge a signature without the signing key. By design, that should not be possible, including in some rather extreme scenarios, like: the adversary chooses billions of messages and can obtain their signatures from a rightful signer; that should not allows making any extra signature for any message, no matter how senseless. In modern systems like ed25519, there's some level of proof of that. –  fgrieu Mar 19 at 16:22
1  
The question is closer to well formed. However Probability in the title and trials in the body of the question suggests an approach where signatures are tried at random until one is acceptable, and that it is asked the (average) number of trials for that strategy to succeed. That number is way to huge for that attack to be worth practical consideration. There are much better attacks to selectively forge ed25519, starting with the obvious one (also the best known AFAIK): finding the private key from the public key using parallelized Pollard Rho, which then allows signature forgery. –  fgrieu Mar 19 at 17:38
1  
"astronomical" is in the right ballpark when trying signatures at random. Penrose estimates the number of baryons in the observable universe to be of the order of $10^{80}$ (1 followed by 80 zeroes), we are talking more zeroes, but not many time more zeroes. –  fgrieu Mar 19 at 17:53
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.