« previous next »
Pages: 1 2 3 [4] 5 6 ... 14   Go Down

Author Topic: New RSA Algorithm discussion  (Read 65486 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 #45 on: July 24, 2010, 09:38:44 am »
Matthias, you are mistaken when you say it is one times mod.  Also, that's not an equal to symbol but a congruence.  (wikipedia)  basically, it means de-1 mod t=<equals>0, where t=<equals>(p-1)(q-1).  In other words, de-1 is evenly divisible by t.  Also look up modular multiplicative inverse on wikipedia.
Logged
+2/-0 karm for this message

Offline matthias1992

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 408
  • Rating: +33/-5
    • View Profile
Re: New RSA Algorithm discussion
« Reply #46 on: July 24, 2010, 10:05:15 am »
Aah ok. my bad. I indeed had mistaken it for a = sign but i didn't notice the extra bar underneath it, it was far past midnight if that is a righteous excuse :P

And on modular arithmetic, I am trying to learn that now, I never had it on school. Maybe the kahnacademy (on youtube) hosts it?

on a off-topic note, the kahnacademy on youtube is a great resource for math you never had or never understood, I can recommend it to everyone. Just hit kahnacademy on YT.

Thanks for the explanation graphmastur.
Logged
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 #47 on: July 24, 2010, 12:20:46 pm »
No problem.  This thread's other purpose, besides finding a new way to break RSA keys, is to explain how it works.  To explain modular arithmetic, it is basically this.

If you have 21 mod 5, that is the remainder of 21 divided by 5, or 1.  If you have 21 mod 4, that also equals 1 because the remainder of 21 divided by 4 equals 1.

Now 221 is congruent to 1 mod 55, because (221-1) mod 55=0.

Does that make sense?
Logged

Offline matthias1992

  • LV6 Super Member (Next: 500)
  • ******
  • Posts: 408
  • Rating: +33/-5
    • View Profile
Re: New RSA Algorithm discussion
« Reply #48 on: July 24, 2010, 12:55:40 pm »
yes it does, thank you.
Logged
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 #49 on: July 26, 2010, 09:05:56 pm »
Glad it does.  So, any ideas for an algorithm?  I'm working on one using a reduced row echelon form of a matrix with the last column being each digit of the number.

Also, are there any recursive or cyclical algorithms for factoring a number?  If so, I would be interested in seeing them. (Note: I do not mean like a simple for loop, or go until a condition is met.)
Logged

Offline bwang

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 634
  • Rating: +30/-11
    • View Profile
Re: New RSA Algorithm discussion
« Reply #50 on: July 26, 2010, 09:13:34 pm »
Here's a very simple "cyclical" algorithm: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
I do not know of any recursive algorithms.
In case anyone is interested, I'll attach my Java QS implementation. It implements the sieving step from the QS, and is utterly useless (because Java is inherently slow) except for educational purposes. It builds the matrix, but I haven't implemented block Lanczos yet.
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #51 on: July 27, 2010, 03:07:49 pm »
Oh, thanks for that.  It will help.  Also, I never understood what the pollard rho algorithm meant by "pseudo-random function modulo n".  I understand modulo n, but what about the pseudo random part?
Logged

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: New RSA Algorithm discussion
« Reply #52 on: July 27, 2010, 03:25:09 pm »
I don't really understand the Pollard-Rho algorithm either, but I think it was meant for numbers with lots of small factors.
Logged

Offline Lionel Debroux

  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2135
  • Rating: +290/-45
    • View Profile
    • TI-Chess Team
Re: New RSA Algorithm discussion
« Reply #53 on: July 27, 2010, 03:31:50 pm »
Indeed, the Pollard Rho heuristic works well for small factors.
Logged
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.
Co-admin of TI-Planet.

Offline bwang

  • LV7 Elite (Next: 700)
  • *******
  • Posts: 634
  • Rating: +30/-11
    • View Profile
Re: New RSA Algorithm discussion
« Reply #54 on: July 27, 2010, 04:24:41 pm »
The "pseudo-random function" is usually simply f(x) = x^2 + 1 mod n. It means that the sequence f(x), f(f(x)), f(f(f(x))), ... behaves like a random sequence.
Logged

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #55 on: July 27, 2010, 05:05:50 pm »
I see.  So basically, it randomly tries to find the factor with a slightly better success rate than just random numbers.
Logged

Offline ExtendeD

  • CoT Emeritus
  • LV8 Addict (Next: 1000)
  • *
  • Posts: 825
  • Rating: +167/-2
    • View Profile
Re: New RSA Algorithm discussion
« Reply #56 on: July 28, 2010, 06:03:55 am »
Quote from: fb39ca4 on July 21, 2010, 12:12:12 pm
When does the OS get validated? At each boot, or just when it is installed?
I've only skimmed through the topic, but the answer posted doesn't seem to be correct. The boot2 and OS signatures are checked at each boot.
Logged
Ndless.me with the finest TI-Nspire programs

Offline jnesselr

  • King Graphmastur
  • LV11 Super Veteran (Next: 3000)
  • ***********
  • Posts: 2270
  • Rating: +81/-20
  • TAO == epic
    • View Profile
Re: New RSA Algorithm discussion
« Reply #57 on: July 28, 2010, 08:08:06 am »
Well, even so, if you crack the rsa key, then it wouldn't make any difference.
Logged

Offline Eeems

  • Mr. Dictator
  • Administrator
  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6268
  • Rating: +318/-36
  • little oof
    • View Profile
    • Eeems
Re: New RSA Algorithm discussion
« Reply #58 on: July 28, 2010, 07:36:07 pm »
I was just thinking, is there any way to create a custom OS receiver and then force the calc to run that OS? so like disable to old OS and use the new one, so then any edits to the new OS that you make will be saved.
« Last Edit: July 28, 2010, 07:36:20 pm by Eeems »
Logged
/e

Offline apcalc

  • The Game
  • CoT Emeritus
  • LV10 31337 u53r (Next: 2000)
  • *
  • Posts: 1393
  • Rating: +120/-2
  • VGhlIEdhbWUh (Base 64 :))
    • View Profile
Re: New RSA Algorithm discussion
« Reply #59 on: July 28, 2010, 07:39:12 pm »
Quote from: Eeems on July 28, 2010, 07:36:07 pm
I was just thinking, is there any way to create a custom OS receiver and then force the calc to run that OS? so like disable to old OS and use the new one, so then any edits to the new OS that you make will be saved.

Well, there is runos, which might do just that, but I am not exactly sure how runos works.  Nevertheless, I doubt that runos will be released.
Logged

Pages: 1 2 3 [4] 5 6 ... 14   Go Up
« previous next »