RSA.sagews

# text to number
def encoding(text):
    result = 0
    for c in text:
        result = 256*result +ord(c)
    return result

# number to text
def decoding(number):
	result = ''
	for i in  number.digits(256):
		result = chr(i) + result
	return result

encoding('HELLOWORLD');

341288709964181938523204

def new_rsa(secur):
	#random primes
	p = random_prime(2^secur, proof=True, lbound=2^(secur-1))
	q = random_prime(2^secur, proof=True, lbound=2^(secur-1))
	N = p*q # product
	if p==q:
		print 'Try again'
		return

	# public key = random coprime to phi(N)
	k1 = 0
	while ( gcd(k1,(p-1)*(q-1)) != 1):
		k1 = ZZ.random_element((p-1)*(q-1)) 

	# private key = inverse modulo phi(N)
	k2 = Integer(Mod(k1,(p-1)*(q-1))^-1)

	print '(Modulus, public key, private key) =', (N,k1,k2)

#random primes
secur=4
p = random_prime(2^secur, proof=True, lbound=2^(secur-1))
q = random_prime(2^secur, proof=True, lbound=2^(secur-1))
N = p*q # product
theta=(p-1)*(q-1)

d1=13
print 'p:',p
print 'q:',q
print 'N:',N
print 'theta:',theta

p: 13 q: 11 N: 143 theta: 120

print gcd(d1,theta)

1

d1=957205063101398429015566884323271990123126993724
d2=8532478929816138548

#only prove correctness up to 1024 bits  
p = 109 
q = 1013 
n = p*q 
phi_n = (p-1)*(q-1) 
while True: 
    e = ZZ.random_element(1,phi_n) 
    if gcd(e,phi_n) == 1:break 
d = lift(Mod(e,phi_n)^(-1))

print e,d,n

51685 35725 110417

p=109
q=1013
n=p*q
theta=(p-1)*(q-1)
d2=8532478929816138548
e2=42811;
d = lift(Mod(d2,theta)^(-1))

Traceback (most recent call last): d = lift(Mod(d2,theta)^(-1)) File "", line 1, in <module> File "/tmp/tmpclbXXj/___code___.py", line 9, in <module> exec compile(u'd = lift(Mod(d2,theta)**(-_sage_const_1 ))' + '\n', '', 'single') File "", line 1, in <module> File "integer_mod.pyx", line 3505, in sage.rings.finite_rings.integer_mod.IntegerMod_int64.__pow__ (sage/rings/finite_rings/integer_mod.c:29447) File "integer_mod.pyx", line 3676, in sage.rings.finite_rings.integer_mod.mod_inverse_int64 (sage/rings/finite_rings/integer_mod.c:30456) ZeroDivisionError: Inverse does not exist.

k1 = 0
while (gcd(k1,(p-1)*(q-1))!= 1):
    k1 = ZZ.random_element((p-1)*(q-1))

kunci=43*427
Hasil=Mod(kunci,(19-1)*(61-1))

print Hasil

1

def rsa(bits): 
    #only prove correctness up to 1024 bits 
    proof = (bits <= 1024) 
    p = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof) 
    q = next_prime(ZZ.random_element(2**(bits//2+1)), proof=proof) 
    n = p*q 
    phi_n = (p-1)*(q-1) 
    while True: 
        e = ZZ.random_element(1,phi_n) 
        if gcd(e,phi_n) == 1:break 
    d = lift(Mod(e,phi_n)^(-1)) 
    return e, d, n

d= random_prime(2^800,lbound=88610040454503918316071773111);
d2=next_prime(d);

print 'd=',d
print 'd2=',d2

d= 2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700601 d2= 2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700713

factor(4460824882019967172592779313)

79 * 904861 * 62403106938069153227

gcd(1850567623300615966303954877,4951760152529835076874141700)

1

%time
p=2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700601
q=2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700713
n=p*q
phi=(p-1)*(q-1)

m = "HelloWorld"
m = map(ord, m);
m = ZZ(list(reversed(m)), 100);

d3=next_prime(7411011497495051)
e2=inverse_mod(d3,phi)
print mod(d3*e2,phi)
ciphertext = power_mod(m,e2,n)
decoded_ciphertext = power_mod(ciphertext,d3,n)
print 'Authentication Password=',decoded_ciphertext==m

d4=next_prime(257472025751104509877298803400268072675887521394599680637130)
e3=inverse_mod(d4,phi)
print mod(d4*e3,phi)
ciphertext1 = power_mod(m,e3,n)
decoded_ciphertext1 = power_mod(ciphertext1,d4,n)
print 'Authentication finger=',decoded_ciphertext1==m
print 'p=',p
print 'q=',q
print 'n=',n
print 'password=',d3
print 'e2=',e2
print 'finger=',d4
print 'e3=',e3
print 'phi=',phi

1 Authentication Password= True 1 Authentication finger= True p= 2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700601 q= 2081221084399694831812956532912337483603222873068352531053211740307009073507124659786409545206381492597261011474734606208518093001357145784599831630221326873499728245103248752835162284232190112952333738604336085778280476955089247171923700713 n= 4331481202149841678429674119923380998923447128614181454357922778194940380590298044421110749802682670436333121610730732948877784233408684436208347869893773582566071572953322629704505666268094809426916883556812143934966710082963909689777382550683261251113824314160660613475419917024322370059955078542232400669231588061751843488004207655134956885100222020466393154356704682677130504746991627548319188653652921492595934493316119357873895344318814614948919454910097452829405597742228513 password= 7411011497495083 e2= 1243535376050220925677669509822938503401880013386775909847179376066302317822661760083878324570556807470455305873456425178516397542596219256223245781356559451546885952613040492916364827473741508212633173175841497745731282019783465285771833979605997374886325207043771315684941487255275243986751356589024098368041849146625930675463254666830584800175712716154925134878430914790510878407922803878088674954647499370616488517533892945874831651662215530779297655106374141654248844531111747 finger= 257472025751104509877298803400268072675887521394599680637241 e3= 2738123034976120551769604413252105521595419256871905176698358975480820326782166616988404338109361455306321872327297607859192401027531461402939017142306546445663267810546467321848738505351258009559036068412914876898385509239764080212798299754856762965700050169624440952067701399217964400691233791786291987213303507728990234262194086733101272470434477319627675623815102984405482299270641878517703702098152424522143068330646214721724850980193208987054035926445836038037979235494858761 phi= 4331481202149841678429674119923380998923447128614181454357922778194940380590298044421110749802682670436333121610730732948877784233408684436208347869893773582566071572953322629704505666268094809426916883556812143934966710082963909689777382546520819082314434650534747547650744949817876623923250016435808920055213441047502523915185117242371971690578199070997180737320518679962838935547328367105665441654196431286098428822991550893493669439651337406276747898349143542650911253894827200 CPU time: 0.04 s, Wall time: 0.05 s

print Integer('0x1c33df8f21c2b854b540bc8040c50af0f4')

9596857686830126572491799251711209173236

m = "Indra123"
m = map(ord, m);
m = ZZ(list(reversed(m)), 100);
print m

6609054950515253

factor(913)

11 * 83

%time
factor(9596857686830126572491799251711209173236)

2^2 * 3 * 31 * 607 * 479639 * 88610040454503918316071773081 CPU time: 0.01 s, Wall time: 0.01 s

np=next_prime(88610040454503918316071773081)

nq=next_prime(np)
print nq

88610040454503918316071773123

p=random_prime(10000)
q=random_prime(10000)
n=p*q
p,q,n
e=17
G=IntegerModRing(lcm(p-1,q-1))
d = G(e)^-1
G(d)*G(e)
m=1337
G2=IntegerModRing(n)
c=G2(m)^e
c
1035365
m_prime=G2(c)^d
m_prime
print d.is_prime()
print e.is_prime()

Traceback (most recent call last): d = G(e)^-1 File "", line 1, in <module> File "/tmp/tmpBAbv87/___code___.py", line 18, in <module> print d.is_prime() File "element.pyx", line 344, in sage.structure.element.Element.__getattr__ (sage/structure/element.c:3874) File "misc.pyx", line 257, in sage.structure.misc.getattr_from_other_class (sage/structure/misc.c:1696) AttributeError: 'sage.rings.finite_rings.integer_mod.IntegerMod_int64' object has no attribute 'is_prime'

print 17.is_prime()

True

#Compute Number Of Bit
import math
def number_of_bits(n):
    return int(math.log(n, 2)) + 1

199410884343017908728815901676685267715533258481123949162148927010860374609434091867762469417096424575370864310779700375177664356499703437138577578584608301919 - 14121291879393255736898193873883666016986408107734625395993132251381852535563339