-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512 Hello everyone! When an adversary attempts to create someone's GPG signature of a certain message, there are at least two ways to do so: 1. Computing the private key from the public key of the target and then using the private key to sign the message; 2. Enumerating the possible signature of that certain message and using the target's public key to verify if one of the signatures is correct. If other conditions are same and the adversary only needs to get the target's signature of one certain message, will the second approach easier than the first approach in terms of computing complexity? I'm really looking forward to the answer and/or further discussion! Thank you! Best, iry -----BEGIN PGP SIGNATURE----- iQIcBAEBCgAGBQJY4HjiAAoJEKFLTbxtzdU8d4QP/2UvpLxY3E2lhN3YVwmQnWMO O/X9svCSsrFLZZU6jskQn0zTTDr05TzYI3xKHOrAocllULMzTHF8Q1X47pUGtdI/ Y2Oa32A387e8bjaSA+iLBuhyfwkRXkNvKy8iwHaG6353i/7hS8EHGugsZYNeXKIv P7wHfaJFZ/7vj4BD4vQZAiLIU0W3jMslHNvNvp1jHSxyiHnM9o+bhdJd7WsqCD6A hAaUP1OAffKSjuM85QpmnsOW29SkkCMVDlyrNtDS58eBup2fxv3YCwzBdH53vnhY tNA5g/KclndmGD5IagacN90hB6cX/LTl55kWDgJdKRqKlMAkhnY4zllWdtM9dcp9 +3NYbWQptxgnfCqVeMLoUew0ioORjDjLulFRHM+X5iNdyanNgCA5H/4wOu4jlb6f dRK8xnzJ4wzVTQONDHDd9B5xQ1cKy1nqi+aeGpmkMJqFmY87ijd32rseWkTe5uKk TYRN8je9RQgLmJ7AYlngTEYw8frsMvprX/zLY88pYe99r2Ggc559yxu9zemqcwpv adWUUbc9ztJybDh4Py7EWSGR/6o2OUAoMlF80petRbDKJbSi/zE/C5HrczKHJkGS cgnW9CQxbJxkePnB6GbGo6tA5TYhcBzJ+8NaCZCFMonkg4ihPIqTLoIIZe/OGYZ4 GK65uMtyc4w8gRjC6sKl =OYVh -----END PGP SIGNATURE----- _______________________________________________ Gnupg-users mailing list [hidden email] http://lists.gnupg.org/mailman/listinfo/gnupg-users |
> 1. Computing the private key from the public key of the target and
> then using the private key to sign the message; The difficulty of this is dependent on the length of the asymmetric key. NIST's guidance is that cracking a 1024-bit key is about 2**80 work, a 2048-bit key is about 2**112 work, and a 3072-bit key is about 2**128 work. > 2. Enumerating the possible signature of that certain message and > using the target's public key to verify if one of the signatures is > correct. I'm not sure what you mean here; that's not how signatures work. Signatures work by computing a digest over data and encrypting that with the private key. Since you lack the private key, you can't generate signatures. What you could do instead is look at an earlier message your target signed, get the digest of that, and generate new messages until you created one with an identical digest. The difficulty of this will depend on your target's signature: DSA-1024: 2**159 work DSA-2048: 2**223 work DSA-3072: 2**255 work RSA: varies by user prefs, but unlikely to be under 2**159 You'll notice the work to break the hash is almost exactly the square of the work to break the key. This is not an accident. :) _______________________________________________ Gnupg-users mailing list [hidden email] http://lists.gnupg.org/mailman/listinfo/gnupg-users |
On Sun, Apr 02, 2017 at 07:12:38PM -0400, Robert J. Hansen wrote:
> > 2. Enumerating the possible signature of that certain message and > > using the target's public key to verify if one of the signatures is > > correct. > > I'm not sure what you mean here; that's not how signatures work. > Signatures work by computing a digest over data and encrypting that with > the private key. Since you lack the private key, you can't generate > signatures. No, but you can generate random numbers and verify whether they happen to be a valid signature. I believe the OP is asking whether it'd be easier to brute-force a signature than it is to brute-force a private key. With RSA, the signature is exactly the same length as the (public) key. Therefore, naively, one could assume that the complexity would be approximately the same too. In practice, however, the work required to brute-force a signature is probably worse than that to brute-force a private key, because the public key must be the product of the private key's two prime numbers (which limits their values to things that can reasonably be the public key's divisors, and you can preselect for that), whereas a signature is a modulus and can therefore be pretty much anything. -- < ron> I mean, the main *practical* problem with C++, is there's like a dozen people in the world who think they really understand all of its rules, and pretty much all of them are just lying to themselves too. -- #debian-devel, OFTC, 2016-02-12 _______________________________________________ Gnupg-users mailing list [hidden email] http://lists.gnupg.org/mailman/listinfo/gnupg-users |
> I believe the OP is asking whether it'd be easier to brute-force a
> signature than it is to brute-force a private key. Unimaginably harder to brute-force a sig. Since RSA is deterministic (at least, naïve RSA is), a sig is done on a digest (of let's say size 256 bits) and there are 2**256 different valid outputs. But the signature length itself is thousands of bits, for 2**thousands of possibilities. So the per-attempt likelihood of finding one of the 2**256 valid signatures out of a signature of 2**thousands of bits is likelihood is 2**(256 - thousands). 2**-2000 is so close to zero as makes no difference whatsoever. _______________________________________________ Gnupg-users mailing list [hidden email] http://lists.gnupg.org/mailman/listinfo/gnupg-users |
Free forum by Nabble | Edit this page |