Author Topic: New RSA Algorithm discussion  (Read 58524 times)

0 Members and 1 Guest are viewing this topic.

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #30 on: July 23, 2010, 04:54:56 pm »
Oh, I see.  What about the idea to use boinc to study the relationships between semiprimes and their factors?

Is it possible? (I mean I know that it is, but could WE do it?)

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: New RSA Algorithm discussion
« Reply #31 on: July 23, 2010, 04:55:27 pm »
What method did you use?

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #32 on: July 23, 2010, 04:56:17 pm »
Yes, Matthias, what method did you use?

Oh, and ninja'd in my last post.

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: New RSA Algorithm discussion
« Reply #33 on: July 23, 2010, 04:59:34 pm »
32 bits is only up to ~4 billion. Not a lot.
1024 bits, on the other hand, goes up to 5e30, or 5 nonillion.
The problem is that, at least with TF, the time increases exponentially.
You're not misunderstanding it, you underestimating how quickly an exponential function grows.
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: New RSA Algorithm discussion
« Reply #34 on: July 23, 2010, 05:04:29 pm »
Ah that would be the reason.  Mathias what language did you use to do this? 

Offline calcdude84se

  • Needs Motivation
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2272
  • Rating: +78/-13
  • Wondering where their free time went...
    • View Profile
Re: New RSA Algorithm discussion
« Reply #35 on: July 23, 2010, 05:05:35 pm »
I would guess Axe, but he might've used ASM. Definitely not BASIC ;D
"People think computers will keep them from making mistakes. They're wrong. With computers you make mistakes faster."
-Adam Osborne
Spoiler For "PartesOS links":
I'll put it online when it does something.

Offline Builderboy

  • Physics Guru
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5673
  • Rating: +613/-9
  • Would you kindly?
    • View Profile
Re: New RSA Algorithm discussion
« Reply #36 on: July 23, 2010, 05:09:20 pm »
If it was Basic i would have definetaly wanted to see *that* code ;D

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #37 on: July 23, 2010, 05:09:58 pm »
Oh yes.  That would be amazing.

Offline matthias1992

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 408
  • Rating: +33/-5
    • View Profile
Re: New RSA Algorithm discussion
« Reply #38 on: July 23, 2010, 05:49:45 pm »
Nah ignore my post, I took a entirely wrong aproach. It was asm btw. I am now studying Euclides algorithm. Shouldn't be too hard to write a asm/vb/c program for. I only have trouble with the last step of the RSA encryption/decryption. I dont understand mod(). Well hopefully someone can explain in layman's language. What I did in my program was just brute forcing every possibilty until a match was found. That match however wasn't encrypted at all. Sorry for the false excitiment. If you don't get my rough explanation of my program just leave it be, it didn't do the trick anyway. I really want to crack this code! :P

eternal fame awaits :D

edit:

If it was Basic i would have definetaly wanted to see *that* code ;D
Code: [Select]
Input "Secret Code:", A
Disp "Code cracked!", "isn't it:",A

somtimes things are really that easy :P
« Last Edit: July 23, 2010, 05:51:56 pm by matthias1992 »
MASM xxxxxxxxxx aborted | SADce ====:::::: 40% -Halted until further notice| XAOS =====::::: 50% -Units done| SKYBOX2D engine ========== 100% -Pre-alpha done. Need to  document it and extend |

~Those who dream by day are cognizant of much more than those who dream by night only. -Sir Edgar Allen Poe-

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #39 on: July 23, 2010, 06:29:22 pm »
Um, not quite. It doesn't actually need to be encrypted or anything. To break the algorithm, you must simply factor the number (which is more difficult the longer it is.)

N mod S means the remainder of N divided by S.

Offline bwang

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 634
  • Rating: +30/-11
    • View Profile
Re: New RSA Algorithm discussion
« Reply #40 on: July 23, 2010, 08:57:59 pm »
@graphmastur: I will try to explain the algorithm:

Shanks-Tonelli modular square root algorithm:
The problem: given n and p, with p prime, find x such that x^2 = n (mod p)
First, a digression. The Legendre symbol (n|p) (actually written in a different manner, but the forum does not support typesetting) is defined as follows: (n|p) = 1 if such an x exists, 0 if p divides n, and -1 otherwise. It can be computed as n^((p-1)/2) mod p.
Now we return to the algorithm:
Step 1: Let p - 1 = 2^s * q , with q odd. This can be done by dividing powers of 2 out of p - 1 until we cannot do so any further.
Step 2: Select z such that (z|p) = -1. We do this simply by randomly selecting z in the set {1, 2, ... p - 1} and computing (z|p) as described above.
Step 3: Let:
                    c = z^q mod p
                    r = n^((q + 1) / 2) mod p
                    t = n^q mod p
                    m = s
Note that all of these values can be computed rapidly using the repeated squaring algorithm.
Step 4: We execute the following loop:
                    While t != 1
                       i = 0
                       tmp = t mod p
                       While tmp != 1
                         tmp = tmp * tmp mod p
                         i = i + 1
                       EndWhile
                       b = c
                       For k = 1 to m - i - 1
                         b  = b * b mod p
                       EndFor
                       r = r * b mod p
                       t = t * b^2 mod p
                       c = b^2 mod p
                       m = i
                    EndWhile
Step 5: Return r

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #41 on: July 23, 2010, 09:54:31 pm »
Thank you so much. That is a lot easier to understand than wikipedia.  Also, I somewhat understand quadratic residues.

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: New RSA Algorithm discussion
« Reply #42 on: July 24, 2010, 02:26:51 am »
Quote
1024 bits, on the other hand, goes up to 5e30, or 5 nonillion.
Actually, ~1.8e308, with factors up to ~1.3e154.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline matthias1992

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 408
  • Rating: +33/-5
    • View Profile
Re: New RSA Algorithm discussion
« Reply #43 on: July 24, 2010, 06:34:02 am »
hmm I studied wikipedia's explanation yesterday and altough I do not quite understand everything I think this:

let d be so that d times e = 1 times mod(_psi_(pq))
couldn't that be:
d=mod(_psi_(pq)) divided by e

forgive me if this is either obvious or stupid, I do math on intuition most of the times :P

Here is a list of most of the required variables (these are the onse I understand):

P = prime (uniformly random to q)
q = prime (uniformly random to p)
Bitlenght P = Bitlenght q
n = p times q
_psi_(n) = (p-1) times (q-1)
e = random(2.....up to x?)

What is the upperbound of e? is it p-1?
once again my apologies if I am asking silly questions again...
MASM xxxxxxxxxx aborted | SADce ====:::::: 40% -Halted until further notice| XAOS =====::::: 50% -Units done| SKYBOX2D engine ========== 100% -Pre-alpha done. Need to  document it and extend |

~Those who dream by day are cognizant of much more than those who dream by night only. -Sir Edgar Allen Poe-

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: New RSA Algorithm discussion
« Reply #44 on: July 24, 2010, 07:53:35 am »
e is fixed, 17 for the 512-bit RSA keys of TI-Z80 and TI-68k calcs and 65537 for the 1024-bit RSA keys of Nspire calcs.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.