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

6 Solutions
3 Solvers

Last Solution submitted on Sep 01, 2019

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 Solvers3

Problem Tags

cryptography large integer calculations

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 Solvers3

Suggested Problems

More from this Author22

Problem Tags

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 Solvers3

Suggested Problems

More from this Author22

Problem Tags

Players