CSAIL2019 Crypto-Puzzle Solver Architecture
Pages 197 - 207
Abstract
The CSAIL2019 time-lock puzzle is an unsolved cryptographic challenge introduced by Ron Rivest in 2019, replacing the solved LCS35 puzzle. Solving these types of puzzles requires large amounts of intrinsically sequential computations (i.e. computations which cannot be parallelized), with each iteration performing a very large (3072-bit in the case of CSAIL2019) modular multiplication operation. The complexity of each iteration is several times greater than known FPGA implementations, and the number of iterations has been increased by about 1000x compared to LCS35. Because of the high complexity of this new puzzle, a number of intermediate, or milestone versions of the puzzle have been specified.
In this paper, we present an FPGA architecture for the CSAIL2019 solver, which we implement on a medium-sized Intel Agilex device. We develop a new multi-cycle modular multiplication method, which is flexible and can fit on a wide variety of sizes of current FPGAs. We also demonstrate a new approach for improving the fitting and timing closure of large, chip-filling arithmetic designs. We used the solver to compute the first 21 out of the 28 milestone solutions of the puzzle, which are the first reported results for this problem.
References
[1]
"Description of the CSAIL2019 Time Capsule Crypto-Puzzle," https://people.csail.mit.edu/rivest/pubs/Riv19f.new-puzzle.txt, accessed: 2022-08--15.
[2]
"Description of the LCS35 Time Capsule Crypto-Puzzle," http://people.csail.mit.edu/rivest/pubs/Riv99b.lcs35-puzzle-description.txt, accessed: 2022-08--15.
[3]
"Programmers Solve MITs 20-year-old Cryptographic Puzzle," https://www.csail.mit.edu/news/programmers-solve-mits-20-yearold-cryptographic-puzzle, accessed: 2022-09--14.
[4]
https://www.supranational.net/, accessed: 2022-09--14.
[5]
"VDF Alliance FPGA competition," https://supranational.atlassian.net/wiki/spaces/VA/pages/36569208/FPGACompetition, accessed: 2021- 06--14.
[6]
E. Öztürk, "Design and implementation of a low-latency modular multiplication algorithm," IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 67, no. 6, pp. 1902--1911, 2020.
[7]
"Amazon EC2 F1 instances," https://aws.amazon.com/ec2/instancetypes/ f1/, accessed: 2022-09--14.
[8]
"Virtex UltraScale product tables," https://www.xilinx.com/products/ silicon-devices/fpga/virtex-ultrascale-plus.html, accessed: 2022-09--14.
[9]
"UltraScale Architecture DSP Slice," https://docs.xilinx.com/v/u/en- US/ug579-ultrascale-dsp, 2021-08--30.
[10]
"VDF Alliance FPGA competition round 1 results and announcements," https://www.vdfalliance.org/news/fpga-competition-round-1- results, 2019--10--31.
[11]
"Pearson round 2," https://github.com/supranational/vdf-fpga-round2- results/tree/master/eric_pearson_2, accessed: 2022-09--14.
[12]
https://blog.janestreet.com/really_low_latency_multipliers_and_ cryptographic_puzzles, 2020-06--22.
[13]
P. L. Montgomery, "Modular multiplication without trial division," Mathematics of Computation, vol. 44, no. 170, pp. 519--521, 1985.
[14]
D. J. Bernstein, Jonathan, and P. Sorenson, "Modular exponentiation via the explicit Chinese Remainder Theorem," pp. 443--454, 2007.
[15]
P. Barrett, "Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard Digital Signal Processor," in Advances in Cryptology - CRYPTO' 86, A. M. Odlyzko, Ed. Berlin, Heidelberg: Springer Berlin Heidelberg, 1987, pp. 311--323.
[16]
A. Karatsuba and Y. Ofman, "Multiplication of multidigit numbers on automata," USSR Academy of Sciences, vol. 145, pp. 293--294, 1962.
[17]
A. D. Booth, "A signed binary multiplication technique," The Quarterly Journal of Mechanics and Applied Mathematics, vol. 4, no. 2, pp. 236--240, 1951. [Online]. Available: http://dx.doi.org/10.1093/qjmam/4.2.236
[18]
https://github.com/supranational/vdf-fpga-round3-results/tree/ master/papers, 2020-01--30.
[19]
Y. Gong and S. Li, "High-throughput FPGA implementation of 256-bit Montgomery modular multiplier," in 2010 Second International Workshop on Education Technology and Computer Science, vol. 3, March 2010, pp. 173--176.
[20]
M. Morales-Sandoval and A. Diaz-Perez, "Scalable GF(p) Montgomery multiplier based on a digit-digit computation approach," IET Computers Digital Techniques, vol. 10, no. 3, pp. 102--109, 2016.
[21]
E. Ozcan and S. S. Erdem, "A high performance full-word Barrett multiplier designed for FPGAs with DSP resources," in 2019 15th Conference on Ph.D Research in Microelectronics and Electronics (PRIME), July 2019, pp. 73--76.
[22]
M. Langhammer and B. Pasca, "Efficient FPGA modular multiplication implementation," in FPGA '21: The 2021 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Virtual Event, USA, February 28 - March 2, 2021, L. Shannon and M. Adler, Eds. ACM, 2021, pp. 217--223. [Online]. Available: https://doi.org/10.1145/3431920.3439306
[23]
F. de Dinechin and B. Pasca, "Large multipliers with fewer DSP blocks," in International Conference on Field Programmable Logic and Applications. IEEE, aug 2009.
[24]
M. Kumm, O. Gustafsson, F. de Dinechin, J. Kappauf, and P. Zipf, "Karatsuba with rectangular multipliers for FPGAs," in 25th IEEE Symposium on Computer Arithmetic, ARITH 2018, Amherst, MA, USA, June 25--27, 2018. IEEE, 2018, pp. 13--20. [Online]. Available: https: //doi.org/10.1109/ARITH.2018.8464809
[25]
E. Vitali, D. Gadioli, F. Ferrandi, and G. Palermo, "Parametric throughput oriented large integer multipliers for high level synthesis," in 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE), 2021, pp. 38--41.
[26]
M. Langhammer and B. Pasca, "Folded integer multiplication for FPGAs," in FPGA '21: The 2021 ACM/SIGDA International Symposium on Field Programmable Gate Arrays, Virtual Event, USA, February 28 - March 2, 2021, L. Shannon and M. Adler, Eds. ACM, 2021, pp. 160--170. [Online]. Available: https://doi.org/10.1145/3431920.3439299
[27]
Intel Stratix®10 GX/SX Device Overview, 2018, https://www.intel.com/ content/dam/www/programmable/us/en/pdfs/literature/hb/stratix- 10/s10-overview.pdf.
[28]
J. Chromczak, M. Wheeler, C. Chiasson, D. How, M. Langhammer, T. Vanderhoek, G. Zgheib, and I. Ganusov, "Architectural enhancements in Intel® Agilex? FPGAs," in FPGA '20: The 2020 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, Seaside, CA, USA, February 23--25, 2020, S. Neuendorffer and L. Shannon, Eds. ACM, 2020, pp. 140--149. [Online]. Available: https://doi.org/10.1145/3373087.3375308
[29]
?UltraFast design methodology guide for Xilinx FPGAs and SoCs," https://docs.xilinx.com/r/2021.2-English/ug949-vivado-designmethodology/ Super-Logic-Region-SLR, 2021--11--19.
[30]
M. Langhammer, S. Gribok, and B. Pasca, ?Low-latency modular exponentiation for FPGAs," IEEE 30th Annual International Symposium on Field- Programmable Custom Computing Machines, 2022.
[31]
Intel Agilex Variable Precision DSP Blocks User Guide, 2019, https://www.intel.com/content/dam/altera-www/global/en_US/ pdfs/literature/hb/agilex/ug-ag-dsp.pdf.
[32]
Intel® Stratix® 10 Variable Precision DSP Blocks User Guide, https://www.intel.com/content/dam/support/us/en/programmable/ support-resources/bulk-container/pdfs/literature/hb/stratix- 10/archives/ug-s10-dsp-18--1.pdf, 2018, 2018-09--24.
[33]
"The On-Line Encyclopedia of Integer Sequences: sequence A141305," https://oeis.org/A141305, accessed: 2022-08--16.
[34]
R. Rivest, Personal communication - April 2022.
[35]
Intel® Agilex?F-Series FPGA Development Kit, https://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&CategoryNo=142& No=1262, 2022, accessed: 2022-09--14.
[36]
Intel® Agilex? Power Analyser, https://www.intel.com/content/www/us/en/support/programmable/support-resources/power/powpowerplay.html, 2022, accessed: 2022-09--14.
[37]
Xilinx Power Estimator User Guide, https://docs.xilinx.com/r/en-US/ ug440, 2022-04-06.
[38]
R. Rivest, personal communication - May 2022.
[39]
Intel Agilex F-Series FPGA and SoC Product Table, 2019, https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/pt/intel-agilex-f-series-product-table.pdf.
Index Terms
- CSAIL2019 Crypto-Puzzle Solver Architecture
Recommendations
CSAIL2019 Crypto-Puzzle Solver Architecture
tThe CSAIL2019 time-lock puzzle is an unsolved cryptographic challenge introduced by Ron Rivest in 2019, replacing the solved LCS35 puzzle. Solving these types of puzzles requires large amounts of intrinsically sequential computations, with each iteration ...
An RSA Encryption Hardware Algorithm Using a Single DSP Block and a Single Block RAM on the FPGA
ICNC '10: Proceedings of the 2010 First International Conference on Networking and ComputingThe main contribution of this paper is to present an efficient hardware algorithm for RSA encryption/decryption based on Montgomery multiplication. Modern FPGAs have a number of embedded DSP blocks (DSP48E1) and embedded memory blocks (BRAM). Our ...
A new modular exponentiation architecture for efficient design of RSA cryptosystem
Modular exponentiation with a large modulus, which is usually accomplished by repeated modular multiplications, has been widely used in public key cryptosystems for secured data communications. To speed up the computation, the Montgomery modular ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
February 2023
283 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 February 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
FPGA '23
Sponsor:
FPGA '23: The 2023 ACM/SIGDA International Symposium on Field Programmable Gate Arrays
February 12 - 14, 2023
CA, Monterey, USA
Acceptance Rates
Overall Acceptance Rate 125 of 627 submissions, 20%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 489Total Downloads
- Downloads (Last 12 months)207
- Downloads (Last 6 weeks)21
Reflects downloads up to 27 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in