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

119 Solutions
12 Solvers

Last Solution submitted on Jun 01, 2022

Last 200 Solutions

Problem Comments

9 Comments

9 Comments

Show 6 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

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

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

look at importing java biginteger

Joel Hottinger on 28 Jul 2021

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

Jeremy Perez on 6 Aug 2021

One should first consider if MATLAB is even adapted for these kinds of calculations. Still, I had a lot of fun.

Solution Comments

Solution 1915449

2 Comments

2 Comments

Tim on 29 Aug 2019

Googling can supplant programming sometimes.

Khanh Dao on 12 Mar 2022

:<<

Problem Recent Solvers12

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 Solvers12

Suggested Problems

More from this Author41

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 Solvers12

Suggested Problems

More from this Author41

Problem Tags

Community Treasure Hunt

Players