New record set for cracking encryption keys

encrypted
Credit: CC0 Public Domain

An international team of computer scientists had set a new record for two of the most important computational problems that are the basis for nearly all of the public-key cryptography that is currently used in the real world.

Public-key cryptography is used in a number of applications including encrypting sensitive and confidential data and . In public-key , keys come in pairs, one public, and one private, and the security of the encryption or digital signature scheme relies on the fact that it is believed to be computationally intractable to compute the private key from the public key. Factoring and discrete logarithm are two of these fundamental problems that are believed to be difficult to solve.

The team factored the largest key yet, a 795-bit integer, and also computed a discrete logarithm of a 795-bit integer. In total, this took them around 35 million hours of computation time.

The key sizes broken by this record computation are not typically used in practice by modern cryptographic applications. However, achieving regular computational records is necessary to update cryptographic security parameters and key size recommendations.

Thanks to algorithmic advances, these calculations have been achieved using much less than had been estimated based on previous records or Moore's law.

The previous records were 768 bits in both cases. The previous factorization record dated from 2010, and the previous discrete logarithm dated from 2016.

Since both the computational records for factoring and discrete log were achieved simultaneously for the same size integers and on the same computational hardware, this work influences the understanding of the scientific community on the relative difficulty of these two problems. It was commonly believed that the problem was at least 10 times more difficult than factoring. This work shows that the difference is much less, on the order of a factor of three.


Explore further

New algorithm shakes up cryptography

More information: Report: 795-bit factoring and discrete logarithms—listserv.nodak.edu/cgi-bin/wa. … BRTHRY;fd743373.1912
Citation: New record set for cracking encryption keys (2019, December 5) retrieved 4 August 2020 from https://techxplore.com/news/2019-12-encryption-keys.html
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.
348 shares

Feedback to editors

User comments