RSA Encryption: Finding Primes to Make Decryption Difficult

  • Context: Graduate 
  • Thread starter Thread starter Zurtex
  • Start date Start date
  • Tags Tags
    Encryption Primes
Click For Summary

Discussion Overview

The discussion revolves around the properties of prime numbers in the context of RSA encryption and the challenges associated with decrypting messages. Participants explore the effectiveness of various factoring methods and express concerns about the security of RSA as encryption techniques evolve.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant inquires about specific types of primes that could complicate RSA decryption.
  • Another participant mentions that RSA is becoming weaker over time and references alternative algorithms like Elliptic Curve Factorization and Pollard's rho techniques.
  • A participant expresses confidence in their peers' limited knowledge of factoring algorithms, suggesting that brute force methods may be predominantly used.
  • There is a clarification that to decode without knowing the keys, one would need to factor pq, as (p-1)(q-1) is not public information.
  • A participant expresses interest in writing an extended essay on RSA and seeks tips from others.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the best methods for breaking RSA encryption or the implications of using different types of primes. Multiple competing views on the security of RSA and alternative encryption methods remain present.

Contextual Notes

Participants express varying levels of understanding of RSA and its underlying principles, with some acknowledging gaps in their knowledge. The discussion includes references to external resources and techniques that may not be universally accepted or validated.

Who May Find This Useful

This discussion may be useful for individuals interested in cryptography, particularly those exploring RSA encryption, factoring methods, and the evolution of encryption techniques.

Zurtex
Science Advisor
Homework Helper
Messages
1,118
Reaction score
1
I'm working on encrypting a small message using RSA. Are there any types of primes or primes of particular property that would make RSA decryption particularly difficult?

Furthermore are there any better ways that just randomly trying to factorise to break RSA encryption or is there some particularly good way?
 
Physics news on Phys.org
Check here,
http://www.rsasecurity.com/rsalabs/node.asp?id=2213

RSA is getting weaker by the day. There are algos like Elliptic Curve Factorisation and pollards rho techniques (this is getting modified by the day to give more and improved pollard rho techniques ... ). Impressive isn't it ?? once the most hardest encryption system is losing ground ... (People are now reverting to Diffie Hellman and El-Gamal these days ... as u can see from the PGP system)

Check here for,
Elliptic Curve Factorisation :
http://www.alpertron.com.ar/ECM.HTM
(brilliant java piece)

Check here for,
Pollard Rho techniques :
http://mathworld.wolfram.com/PollardRhoFactorizationMethod.html
http://planetmath.org/encyclopedia/PollardsRhoMethod.html

-- AI
 
Last edited by a moderator:
Wow! Thanks, I don't have to worry too much as I am a Freshmen who is far more into maths than any of my fellow class mates, so with a bit of luck the only algorthm they'll use to test for primes is the very traditional brute force.

The program is very impressive, it can factorise quicker than MATLAB can multiply the factors.

I’m still a little unsure about RSA though, will I be factorising pq or (p-1)(q-1)? Still grappling with the understanding the theory a bit (mind you I’m reading several weeks ahead of the lectures so no big deal yet).

Edit: Dosn't really matter, I'll read it all up. Thanks again :smile:
 
Last edited:
If you want to decode it without knowing the keys you will factorise pq since it is public (p-1)(q-1) is not public.
I'm in the Ib diploma program and I'm thinking of writing an extended essey about RSA. Do you have any tips?
/Andreas
 

Similar threads

Warning: Bad actors may already be in store-now-decrypt-later mode
  • · Replies 5 ·
Replies
5
Views
2K
Comp Sci RSA to encrypt English Alphabets, any restrictions?
  • · Replies 7 ·
Replies
7
Views
2K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Graduate Trying to Develop a Decryption Scheme for a Given Encryption
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Can De Branges' Theorem Make Factoring Prime Numbers Easier for RSA Encryption?
  • · Replies 6 ·
Replies
6
Views
4K
A historical look at decrypting the Enigma
  • · Replies 52 ·
2
Replies
52
Views
7K
Undergrad How Do Properties of Modulus Algebra Apply to RSA and Diffie-Hellman?
  • · Replies 12 ·
Replies
12
Views
3K
Comp Sci Weird File Output behavior in java
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Modular Arithmetic - RSA Encryption
  • · Replies 3 ·
Replies
3
Views
3K
Graduate Extended Goldbach: every odd number the sum of 5 primes
  • · Replies 1 ·
Replies
1
Views
4K