Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Created by David Hill

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Given two prime number character strings (p and q), generate the RSA public and private keys (n and d) with e = 65537. The more difficult part is doing this without the use of symbolic numbers. Example: p = '3355335697481001330501721', q = '5955344080483688912855719' n='19982178584029090861856118769095354822153154192399' d='3270348772331599380262578849367006078599068947553'</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:hyperlink w:docLocation=\"https://simple.wikipedia.org/wiki/RSA_algorithm\"><w:r><w:t>&lt;https://simple.wikipedia.org/wiki/RSA_algorithm</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

47 Solutions
4 Solvers

Last Solution submitted on Feb 25, 2021

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older comment

Tim on 28 Aug 2019

I get different results for d in test cases 2, 3, and 4 (in particular, d=929660805638728623653 for test case 2).

David Hill on 28 Aug 2019

This was my first Cody problem and I had a mistake in the assert within the test cases. I fixed the problem. Previously the assert was looking for [n,d] combined into a single character array. I have tested the test cases and they are correct. You should use the Euclidean algorithm.

Tim on 28 Aug 2019

If I understand correctly, we should have mod(d*e,phi)=1, where phi=(p-1)*(q-1). My answers seem to satisfy that condition, but test cases 2, 3, and 4 do not.

David Hill on 28 Aug 2019

Tim, you are absolutely correct. Thanks for the comment. I fixed the test cases.

Solution Comments

Solution 1915449

1 Comment

1 Comment

Tim on 29 Aug 2019

Googling can supplant programming sometimes.

Problem Recent Solvers4

Problem Tags

cryptography large integer calculations

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author30

Problem Tags

Community Treasure Hunt

Problem 44956. Determine RSA keys (public and private) given two prime number character strings (p and q)

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author30

Problem Tags

Community Treasure Hunt

Players