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

108 Solutions
7 Solvers

Last Solution submitted on Jul 28, 2021

Last 200 Solutions

Problem Comments

8 Comments

8 Comments

Show 5 older comments

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.

Joel Hottinger on 9 Jul 2021 at 14:49

Could someone help me out with the modular inversion. I can't seem to get it to work for any large numbers. I've been stuck for a while

Joel Hottinger on 9 Jul 2021 at 15:39

I think my main issue is that I cannot use the mod function with large numbers, what is a way around this?

David Hill on 27 Jul 2021 at 21:50

look at importing java biginteger

Joel Hottinger on 28 Jul 2021 at 15:37

@David Hill. Thanks, that worked a lot better for me

Solution Comments

Solution 1915449

1 Comment

1 Comment

Tim on 29 Aug 2019

Googling can supplant programming sometimes.

Problem Recent Solvers7

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 Solvers7

Suggested Problems

More from this Author35

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 Solvers7

Suggested Problems

More from this Author35

Problem Tags

Community Treasure Hunt

Players