Large Prime

Agnishom · 2013-09-23 13:47:40

anonimnystefy wrote:

Is there something more simple we could try first?

Should we compare the secrets?

anonimnystefy · 2013-09-23 13:49:19

Hm, we could. But, I will be able to do that after I get my good night's sleep.

Agnishom · 2013-09-23 13:55:49

Isn't it already 3 o clock there? Do you remain awake for so long?

Anyway, goodnight

Agnishom · 2013-09-23 15:00:28

http://pastebin.com/MyZtxUyu

import base64
def rc4crypt(data, key):
    x = 0
    box = range(256)
    for i in range(256):
        x = (x + box[i] + ord(key[i % len(key)])) % 256
        box[i], box[x] = box[x], box[i]
    x,y = 0, 0
    out = []
    for char in data:
        x = (x + 1) % 256
        y = (y + box[x]) % 256
        box[x], box[y] = box[y], box[x]
        out.append(chr(ord(char) ^ box[(box[x] + box[y]) % 256]))
    return ''.join(out)
    
def decode(message,key):
    return rc4crypt(base64.b64decode(message),key)
def encode(message,key):
	return base64.b64encode(rc4crypt(message,key))

key = raw_input('Enter secret here:\n')
message = raw_input('Enter message here:\n')

print 'If you wanted to encrypt, here\'s the cyphertext:', encode(message,key)
try:
	print 'If you wanted to decrypt, here\'s the plaintext:', decode(message,key)
except:
	pass

Instructions
1. Paste the above python code in a file and run in a python interpreter if you have one, else paste it to
a. ideone
b. repl.it
2. The program takes 2 lines of input from stdin. The first line accepts the secret and the second line accepts the cyphertext or plaintext
3. Enter your secret in the exact decimal form(because I could not find a better way, this should work until we get something better). For example, if your secret is 7000123, you just type in 7000123(or copypasta it).
4. Running it on a interpreter or on repl.it will prompt you to enter the secret and the message when you are expected to do so.
5. To run it on ideone, you are supposed to enter the secret and the message seperated by a newline in the stdin field before running the program.

bobbym · 2013-09-23 21:44:24

Could you post the link to the video?

http://www.youtube.com/watch?v=40i9ujVJ040

anonimnystefy · 2013-09-23 22:37:15

nhmIfQZuJaeccvW/WqEvpFAHfI5I1yqkSXLLbZ0uhH8g

Agnishom · 2013-09-24 00:08:13

anonimnystefy wrote:

nhmIfQZuJaeccvW/WqEvpFAHfI5I1yqkSXLLbZ0uhH8g

jxXbHUFJOPSGePnyFptuvR8MeIhJkg==

anonimnystefy · 2013-09-24 00:19:40

jxXbHUFJOPSGePnyFptuvR8MeIhJkg==

nwSIWA5lP/XUVOy5CcI8rxESf4JI0CCoSjc=

Agnishom · 2013-09-24 00:29:22

anonimnystefy wrote:

nwSIWA5lP/XUVOy5CcI8rxESf4JI0CCoSjc=

khnMHBhvOfSBbv2+E4YrpR4bM5obky6pBn/AOYw0nX56Yc5bvQ==

auyeungyat · 2013-09-24 03:23:18

yes,I want a Terminal code.Thank you!

Agnishom · 2013-09-24 03:41:31

Hi;

What do you want a terminal code for?
If you're on mac, you probably already have python.
I have never used a mac, I do not know about the mac terminal. Still, I believe that I could help if I knew what code you need

danaj · 2014-03-14 17:56:17

I'm not sure if I should post, (1) it is somewhat necro-posting, (2) there seems to be another conversation going on about DH, and (3) I type way too much. But regarding generating large primes, this is a good paper about generating n-bit random primes: "Close to Uniform Prime Number Generation With Fewer Random Bits" by Fouque and Tibouchi available at eprint.iacr.org/2011/481. For crypto, you may want to also look at FIPS 186-4.

PRIMEINC: generate a random number in the range, run next_prime on it. Simple and fast, but bad distribution.

Trivial: Aka Monte Carlo method as in post 3. Perfectly uniform, but uses excessive randomness and is very slow for large sizes. A comment about the post 3 code: for sizes over 2 bits, you'd want to take n-2 random bits and then set bits n-1 and 0 -- there is no need to waste time and entropy testing even numbers. A well written test will return almost instantly, but you wasted time getting all those bits -- if you're on an isolated headless server using /dev/random you may wait hours to get the next set.

Modified: Methods like Fouque and Tibouchi A1 or A2; Joye-Paillier, etc. I use a somewhat similar method for odd ranges (e.g. for ranges not a power of 2). These sacrifice some uniformity for big increases in speed and less entropy consumption. (the entropy consumption may or may not matter to you, but sometimes it is important).

Provable primes, typically Shawe-Taylor or Maurer's FastPrime. Common for crypto use. You can find Shawe-Taylor in FIPS 186-4; Maurer's algorithm in his publicly available paper, Menezes's book, or various open source implementations. These work by generating a small random prime using the trivial method, then generating a larger one by iterating with additional random input until proven with either Pocklington or its improved version from BLS theorem 3. Then recurse to make successively larger primes. They only generate a subset of the primes in the range (10% for Maurer's FastPrime, substantially less for Shawe-Taylor) but that typically doesn't matter.

openssl or other software. Good and bad. OpenSSL likely doesn't make some mistakes you may make. But you have to make sure your platform has a recent version, your program actually calls the right executable, you send it the right arguments, you interpret the output and exceptions properly, you're ok with its decisions on randomness sources, you're OK with it not meeting FIPS 186-4 standards for primality testing, and know it is slower for sizes > 1024 than what can be done with GMP meeting the standards.

There are lots of other considerations. E.g. where are you getting your randomness? Are you using a good enough primality test for your purpose? Do you need provable primes? Strong primes? Writing your own code is fun, but may have bugs -- do lots of testing.

Whether these are "quick" or not depends on the size, which method you choose, your implementations, and what you think quick means. For 1024-bit primes, my older machine using Perl code generates them in 0.06s each (F&T algorithm 1, ISAAC seeded from /dev/random, BPSW + 1 M-R probable primes). Add 0.006s for 3 additional random M-R plus a Frobenius test. Add not much more for enough extra M-R tests to make FIPS 186-4 happy. For smaller sizes sometimes running a primality proof on the n-bit prime is faster than a constructive method, but your mileage may vary. At 1024 bits, my Maurer routine takes 0.65s, while Shawe-Taylor using FIPS 186-4 + SHA256 takes 0.24s. The generation code is in Perl so it could be faster, but the heavy work ends up being in C+GMP.

Math Is Fun Forum

#26 2013-09-23 13:47:40

Re: Large Prime

#27 2013-09-23 13:49:19

Re: Large Prime

#28 2013-09-23 13:55:49

Re: Large Prime

#29 2013-09-23 15:00:28

Re: Large Prime

#30 2013-09-23 21:44:24

Re: Large Prime

#31 2013-09-23 22:37:15

Re: Large Prime

#32 2013-09-24 00:08:13

Re: Large Prime

#33 2013-09-24 00:19:40

Re: Large Prime

#34 2013-09-24 00:29:22

Re: Large Prime

#35 2013-09-24 03:23:18

Re: Large Prime

#36 2013-09-24 03:41:31

Re: Large Prime

#37 2014-03-14 17:56:17

Re: Large Prime

Board footer