(Frankly, I'm way to stupid to even understand half the words
)an observation
Re: an observation
I looooove this thread! Everytime I don't feel tired enough to go to sleep, I go and re-read it from start to finish!
(Frankly, I'm way to stupid to even understand half the words )
(Frankly, I'm way to stupid to even understand half the words
)( PB6.00 LTS Win11 x64 Asrock AB350 Pro4 Ryzen 5 3600 32GB GTX1060 6GB)
( The path to enlightenment and the PureBasic Survival Guide right here... )
( The path to enlightenment and the PureBasic Survival Guide right here... )
Re: an observation
okie let me clarify my moronic stance
dude here says
I have a nice table of totient functions and I have this property
let e and d be 2 numbers which satisfy the following:
e.d = 1 mod Phi( p)
(p is product of 2 primes) (e and d have to satisfy some relationship of the euler totient function Phi)
then
(anynumber)^ed mod p = anynumber
hence
((anynumber)^e mod p ) ^d mod p = anynumber
I call the public key as e and p
and d as the private key
so anyone sending me the message has to do
anynumber^e mod p = encryptedmessage
I then get back the original message by doing
encryptedmessage^d mod p = anynumber
my point is this
if I know
e and p,
I also know
e.d = kPhi(p) +1 where k is some integer
Phi(p)=P
so to find "d" I need to solve the possible solutions of
e.d -kP=1
Note this is the same as solving the above using Euclidian algorithm or any fast computing method
I hope that clarifies my posts
e ,p and d are very large numbers (1024 bits) so the best thing to use to find solutions using string math kind of methods to solve
e.d - k.P=1
1 possible algo is what I have posted above (the 10x-21y =1 example)
dude here says
I have a nice table of totient functions and I have this property
let e and d be 2 numbers which satisfy the following:
e.d = 1 mod Phi( p)
(p is product of 2 primes) (e and d have to satisfy some relationship of the euler totient function Phi)
then
(anynumber)^ed mod p = anynumber
hence
((anynumber)^e mod p ) ^d mod p = anynumber
I call the public key as e and p
and d as the private key
so anyone sending me the message has to do
anynumber^e mod p = encryptedmessage
I then get back the original message by doing
encryptedmessage^d mod p = anynumber
my point is this
if I know
e and p,
I also know
e.d = kPhi(p) +1 where k is some integer
Phi(p)=P
so to find "d" I need to solve the possible solutions of
e.d -kP=1
Note this is the same as solving the above using Euclidian algorithm or any fast computing method
I hope that clarifies my posts
e ,p and d are very large numbers (1024 bits) so the best thing to use to find solutions using string math kind of methods to solve
e.d - k.P=1
1 possible algo is what I have posted above (the 10x-21y =1 example)
Re: an observation
a simple implementation using inline asm:
using the commented part ( a real example) takes approx 5 days for the code to spit out something, however this helps demonstrate the approach...
logic as follows:
1. given message ^e mod pq = encrypted message
2. d is not known, find d, e and pq are known mesage^ed mod pq = message mod pq is what we want, hence message^ed-1 mod pq =0; let ed=number
3. we assume message is "2" and hence 2^number mod pq = 2 mod pq
4. so we need to find (2.(2^number-1) -1 ))mod pq =0 ...this is easy let: number -1 = something ( or k times something, as basically we need to find "F" where 2^F mod pq =1 mod pq and then compute multiples of F to satisfy the 1st case)
to compute: ((2^something) -1) mod pq =0
we know (2^something) -1 is of the form 1111111111............
so we know if ((2^something) -1) mod pq =0 then "something" can be used to compute our result
so we start with 11 and then keep putting in <<1 (left shift) till we start getting "something" and divide by pq (repetitive subtract) till remainder is zero
5. we iterate on "something" using the code below (variable cnt is what we need to know, intially cnt =2 for 011)
6. once we know "something" we can easily solve
k. (something)+1 = d.e
k and d are unknown, fairly easy to compute
the example below is from the wiki
https://en.wikipedia.org/wiki/RSA_(cryp ... m)#Example
code works using asm very simple and churns out 780 immediately (rest are all multiples of 780)
so k.780+1=17.d is a candidate (the rest are all multiples of 780)
we see that k=60 gives us d as needed.
However any possible solution of the above giving a + integer d and a + integer k is a valid decryption key, for example d=413 would work just as well as a decryption key- because is satisfies the totient modulus unity identity (k=9)
using the commented part ( a real example) takes approx 5 days for the code to spit out something, however this helps demonstrate the approach...
logic as follows:
1. given message ^e mod pq = encrypted message
2. d is not known, find d, e and pq are known mesage^ed mod pq = message mod pq is what we want, hence message^ed-1 mod pq =0; let ed=number
3. we assume message is "2" and hence 2^number mod pq = 2 mod pq
4. so we need to find (2.(2^number-1) -1 ))mod pq =0 ...this is easy let: number -1 = something ( or k times something, as basically we need to find "F" where 2^F mod pq =1 mod pq and then compute multiples of F to satisfy the 1st case)
to compute: ((2^something) -1) mod pq =0
we know (2^something) -1 is of the form 1111111111............
so we know if ((2^something) -1) mod pq =0 then "something" can be used to compute our result
so we start with 11 and then keep putting in <<1 (left shift) till we start getting "something" and divide by pq (repetitive subtract) till remainder is zero
5. we iterate on "something" using the code below (variable cnt is what we need to know, intially cnt =2 for 011)
6. once we know "something" we can easily solve
k. (something)+1 = d.e
k and d are unknown, fairly easy to compute
the example below is from the wiki
https://en.wikipedia.org/wiki/RSA_(cryp ... m)#Example
code works using asm very simple and churns out 780 immediately (rest are all multiples of 780)
so k.780+1=17.d is a candidate (the rest are all multiples of 780)
we see that k=60 gives us d as needed.
However any possible solution of the above giving a + integer d and a + integer k is a valid decryption key, for example d=413 would work just as well as a decryption key- because is satisfies the totient modulus unity identity (k=9)
Code: Select all
Global Dim a.i(1024/32)
Global unity_found=0
For i= 0 To 31
;a(i)=%11111111111111111111111111111111
a(i)=0
Next i
#DEBUG=0
OpenConsole()
Global dummy.i=%0
Global cnt=2
;t1-t32 and s1-s32 are 32 registers of 32 bits each; totally treat as one 1024 bit register
Global c.b=%0 ; this is the carry
Global t1.i=a(0)
;Debug Bin(t1)
Global t2.i=a(1)
Global t3.i=a(2)
Global t4.i=a(3)
Global t5.i=a(4)
Global t6.i=a(5)
Global t7.i=a(6)
Global t8.i=a(7)
Global t9.i=a(8)
Global t10.i=a(9)
Global t11.i=a(10)
Global t12.i=a(11)
Global t13.i=a(12)
Global t14.i=a(13)
Global t15.i=a(14)
Global t16.i=a(15)
Global t17.i=a(16)
Global t18.i=a(17)
Global t19.i=a(18)
Global t20.i=a(19)
Global t21.i=a(20)
Global t22.i=a(21)
Global t23.i=a(22)
Global t24.i=a(23)
Global t25.i=a(24)
Global t26.i=a(25)
Global t27.i=a(26)
Global t28.i=a(27)
Global t29.i=a(28)
Global t30.i=a(29)
Global t31.i=a(30)
Global t32.i=%00000000000000000000000000000011
;Global s1.i=%10110100001100011001100000001010
Global s1=t1
;Global s2.i=%11000100101111000110001011000001
Global s2=t2
;Global s3.i=%10001000101010101101110010110000
Global s3=t3
;Global s4.i=%11001000101110110011001100110101
Global s4=t4
;Global s5.i=%00011001110101010000110001100100
Global s5=t5
;Global s6.i=%10111001001111010100000110110010
Global s6=t6
;Global s7.i=%10010110111111001111001100110001
Global s7=t7
;Global s8.i=%11100001011001100011011011010000
Global s8=t8
;Global s9.i=%10001110010101100001001001000100
Global s9=t9
;Global s10.i=%10111010011101011110101111101000
Global s10=t10
;Global s11.i=%00011100100111000101101101100110
Global s11=t11
;Global s12.i=%01110000001100110101001000010100
Global s12=t12
;Global s13.i=%11001001111011000100111110010001
Global s13=t13
;Global s14.i=%01010001011100000011100111011110
Global s14=t14
;Global s15.i=%01010011100001010001011100010110
Global s15=t15
Global s16=t16
Global s17=t17
Global s18=t18
Global s19=t19
Global s20=t20
Global s21=t21
Global s22=t22
Global s23=t23
Global s24=t24
Global s25=t25
Global s26=t26
Global s27=t27
Global s28=t28
Global s29=t29
Global s30=t30
Global s31=t31
Global s32=%110010100001
Global x=s32
;Global s16.i=%10010100011011101110111011110100
;Global s17.i=%11010101011011111101010111001010
;Global s18.i=%10110011010001110101111000011011
;Global s19.i=%00001100011110111100010111001100
;Global s20.i=%00101011011010111100000110010000
;Global s21.i=%11000011000101100011000100001101
;Global s22.i=%10111111011110101100011101000111
;Global s23.i=%01110111100011111010000000100001
;Global s24.i=%11000111010011001101000000010110
;Global s25.i=%01100101000000001100000100001111
;Global s26.i=%11010111101110001000000011100011
;Global s27.i=%11010010011101010110101111000001
;Global s28.i=%11101010100111100101110001011100
;Global s29.i=%11101010011111011100000110100001
;Global s30.i=%00010000101111001011100011101000
;Global s31.i=%00110101000111001001111000100111
;Global s32.i=%01010010011111100100000110001111
CLC
If #DEBUG
Debug t1
EndIf
CLC
If #DEBUG
Debug s1
EndIf
CLC
;subtraction below
Loop:
;Debug "loop"
MOV EAX,t32
SBB EAX,s32
MOV s32,EAX
MOV EAX,t31
SBB EAX,s31
MOV s31,EAX
MOV EAX,t30
SBB EAX,s30
MOV s30,EAX
MOV EAX,t29
SBB EAX,s29
MOV s29,EAX
MOV EAX,t28
SBB EAX,s28
MOV s28,EAX
MOV EAX,t27
SBB EAX,s27
MOV s27,EAX
MOV EAX,t26
SBB EAX,s26
MOV s26,EAX
MOV EAX,t25
SBB EAX,s25
MOV s25,EAX
MOV EAX,t24
SBB EAX,s24
MOV s24,EAX
MOV EAX,t23
SBB EAX,s23
MOV s23,EAX
MOV EAX,t22
SBB EAX,s22
MOV s22,EAX
MOV EAX,t21
SBB EAX,s21
MOV s21,EAX
MOV EAX,t20
SBB EAX,s20
MOV s20,EAX
MOV EAX,t19
SBB EAX,s19
MOV s19,EAX
MOV EAX,t18
SBB EAX,s18
MOV s18,EAX
MOV EAX,t17
SBB EAX,s17
MOV s17,EAX
MOV EAX,t16
SBB EAX,s16
MOV s16,EAX
MOV EAX,t15
SBB EAX,s15
MOV s15,EAX
MOV EAX,t14
SBB EAX,s14
MOV s14,EAX
MOV EAX,t13
SBB EAX,s13
MOV s13,EAX
MOV EAX,t12
SBB EAX,s12
MOV s12,EAX
MOV EAX,t11
SBB EAX,s11
MOV s11,EAX
MOV EAX,t10
SBB EAX,s10
MOV s10,EAX
MOV EAX,t9
SBB EAX,s9
MOV s9,EAX
MOV EAX,t8
SBB EAX,s8
MOV s8,EAX
MOV EAX,t7
SBB EAX,s7
MOV s7,EAX
MOV EAX,t6
SBB EAX,s6
MOV s6,EAX
MOV EAX,t5
SBB EAX,s5
MOV s5,EAX
MOV EAX,t4
SBB EAX,s4
MOV s4,EAX
MOV EAX,t3
SBB EAX,s3
MOV s3,EAX
MOV EAX,t2
SBB EAX,s2
MOV s2,EAX
MOV EAX,t1
SBB EAX,s1
MOV s1,EAX
SETC c
;If cnt=17
;PrintN(Str(t1))
;EndIf
If #DEBUG Or cnt=46800
Debug "start"
Debug Right(Bin(s1),32)
Debug Right(Bin(s2),32)
Debug Right(Bin(s3),32)
Debug Right(Bin(s4),32)
Debug Right(Bin(s5),32)
Debug Right(Bin(s6),32)
Debug Right(Bin(s7),32)
Debug Right(Bin(s8),32)
Debug Right(Bin(s9),32)
Debug Right(Bin(s10),32)
Debug Right(Bin(s11),32)
Debug Right(Bin(s12),32)
Debug Right(Bin(s13),32)
Debug Right(Bin(s14),32)
Debug Right(Bin(s15),32)
Debug Right(Bin(s16),32)
Debug Right(Bin(s17),32)
Debug Right(Bin(s18),32)
Debug Right(Bin(s19),32)
Debug Right(Bin(s20),32)
Debug Right(Bin(s21),32)
Debug Right(Bin(s22),32)
Debug Right(Bin(s23),32)
Debug Right(Bin(s24),32)
Debug Right(Bin(s25),32)
Debug Right(Bin(s26),32)
Debug Right(Bin(s27),32)
Debug Right(Bin(s28),32)
Debug Right(Bin(s29),32)
Debug Right(Bin(s30),32)
Debug Right(Bin(s31),32)
Debug Right(Bin(s32),32)
Debug "end"
Debug c
EndIf
If s1=0 And s2=0 And s3=0 And s4=0 And s5=0 And s6=0 And s7=0 And s8=0 And s9=0 And s10=0 And s11=0 And s12=0 And s13=0 And s14=0 And s15=0 And s16=0 And s17=0 And s18=0 And s19=0 And s20=0 And s21=0 And s22=0 And s23=0 And s24=0 And s25=0 And s26=0 And s27=0 And s28=0 And s29=0 And s30=0 And s31=0 And s32=0
PrintN(Str(cnt))
Input()
Else
unity_found=0
EndIf
If c=0 And unity_found=0
t1=s1
t2=s2
t3=s3
t4=s4
t5=s5
t6=s6
t7=s7
t8=s8
t9=s9
t10=s10
t11=s11
t12=s12
t13=s13
t14=s14
t15=s15
t16=s16
t17=s17
t18=s18
t19=s19
t20=s20
t21=s21
t22=s22
t23=s23
t24=s24
t25=s25
t26=s26
t27=s27
t28=s28
t29=s29
t30=s30
t31=s31
t32=s32
;Global s1.i=%10110100001100011001100000001010
;Global s2.i=%11000100101111000110001011000001
;Global s3.i=%10001000101010101101110010110000
;Global s4.i=%11001000101110110011001100110101
;Global s5.i=%00011001110101010000110001100100
;Global s6.i=%10111001001111010100000110110010
;Global s7.i=%10010110111111001111001100110001
;Global s8.i=%11100001011001100011011011010000
;Global s9.i=%10001110010101100001001001000100
;Global s10.i=%10111010011101011110101111101000
;Global s11.i=%00011100100111000101101101100110
;Global s12.i=%01110000001100110101001000010100
;Global s13.i=%11001001111011000100111110010001
;Global s14.i=%01010001011100000011100111011110
;Global s15.i=%01010011100001010001011100010110
;Global s16.i=%10010100011011101110111011110100
;Global s17.i=%11010101011011111101010111001010
;Global s18.i=%10110011010001110101111000011011
;Global s19.i=%00001100011110111100010111001100
;Global s20.i=%00101011011010111100000110010000
;Global s21.i=%11000011000101100011000100001101
;Global s22.i=%10111111011110101100011101000111
;Global s23.i=%01110111100011111010000000100001
;Global s24.i=%11000111010011001101000000010110
;Global s25.i=%01100101000000001100000100001111
;Global s26.i=%11010111101110001000000011100011
;Global s27.i=%11010010011101010110101111000001
;Global s28.i=%11101010100111100101110001011100
;Global s29.i=%11101010011111011100000110100001
;Global s30.i=%00010000101111001011100011101000
;Global s31.i=%00110101000111001001111000100111
;Global s32.i=%01010010011111100100000110001111
;Global s1.i=%10110100001100011001100000001010
Global s1=0
;Global s2.i=%11000100101111000110001011000001
Global s2=0
;Global s3.i=%10001000101010101101110010110000
Global s3=0
;Global s4.i=%11001000101110110011001100110101
Global s4=0
;Global s5.i=%00011001110101010000110001100100
Global s5=0
;Global s6.i=%10111001001111010100000110110010
Global s6=0
;Global s7.i=%10010110111111001111001100110001
Global s7=0
;Global s8.i=%11100001011001100011011011010000
Global s8=0
;Global s9.i=%10001110010101100001001001000100
Global s9=0
;Global s10.i=%10111010011101011110101111101000
Global s10=0
;Global s11.i=%00011100100111000101101101100110
Global s11=0
;Global s12.i=%01110000001100110101001000010100
Global s12=0
;Global s13.i=%11001001111011000100111110010001
Global s13=0
;Global s14.i=%01010001011100000011100111011110
Global s14=0
;Global s15.i=%01010011100001010001011100010110
Global s15=0
Global s16=0
Global s17=0
Global s18=0
Global s19=0
Global s20=0
Global s21=0
Global s22=0
Global s23=0
Global s24=0
Global s25=0
Global s26=0
Global s27=0
Global s28=0
Global s29=0
Global s30=0
Global s31=0
Global s32=%110010100001
Goto LOOP
ElseIf c=1
;Debug "c=1"
STC
RCL t32,1
RCL t31,1
RCL t30,1
RCL t29,1
RCL t28,1
RCL t27,1
RCL t26,1
RCL t25,1
RCL t24,1
RCL t23,1
RCL t22,1
RCL t21,1
RCL t20,1
RCL t19,1
RCL t18,1
RCL t17,1
RCL t16,1
RCL t15,1
RCL t14,1
RCL t13,1
RCL t12,1
RCL t11,1
RCL t10,1
RCL t9,1
RCL t8,1
RCL t7,1
RCL t6,1
RCL t5,1
RCL t4,1
RCL t3,1
RCL t2,1
RCL t1,1
SETC c
;Debug Right(Bin(t32),32)
cnt=cnt+1
PrintN (Str(cnt))
If #DEBUG
Debug "shifted"
Debug Right(Bin(t1),32)
Debug Right(Bin(t2),32)
Debug Right(Bin(t3),32)
Debug Right(Bin(t4),32)
Debug Right(Bin(t5),32)
Debug Right(Bin(t6),32)
Debug Right(Bin(t7),32)
Debug Right(Bin(t8),32)
Debug Right(Bin(t9),32)
Debug Right(Bin(t10),32)
Debug Right(Bin(t11),32)
Debug Right(Bin(t12),32)
Debug Right(Bin(t13),32)
Debug Right(Bin(t14),32)
Debug Right(Bin(t15),32)
Debug Right(Bin(t16),32)
Debug Right(Bin(t17),32)
Debug Right(Bin(t18),32)
Debug Right(Bin(t19),32)
Debug Right(Bin(t20),32)
Debug Right(Bin(t21),32)
Debug Right(Bin(t22),32)
Debug Right(Bin(t23),32)
Debug Right(Bin(t24),32)
Debug Right(Bin(t25),32)
Debug Right(Bin(t26),32)
Debug Right(Bin(t27),32)
Debug Right(Bin(t28),32)
Debug Right(Bin(t29),32)
Debug Right(Bin(t30),32)
Debug Right(Bin(t31),32)
Debug Right(Bin(t32),32)
Debug "end"
Debug c
EndIf
;Global s1.i=%10110100001100011001100000001010
;Global s2.i=%11000100101111000110001011000001
;Global s3.i=%10001000101010101101110010110000
;Global s4.i=%11001000101110110011001100110101
;Global s5.i=%00011001110101010000110001100100
;Global s6.i=%10111001001111010100000110110010
;Global s7.i=%10010110111111001111001100110001
;Global s8.i=%11100001011001100011011011010000
;Global s9.i=%10001110010101100001001001000100
;Global s10.i=%10111010011101011110101111101000
;Global s11.i=%00011100100111000101101101100110
;Global s12.i=%01110000001100110101001000010100
;Global s13.i=%11001001111011000100111110010001
;Global s14.i=%01010001011100000011100111011110
;Global s15.i=%01010011100001010001011100010110
;Global s16.i=%10010100011011101110111011110100
;Global s17.i=%11010101011011111101010111001010
;Global s18.i=%10110011010001110101111000011011
;Global s19.i=%00001100011110111100010111001100
;Global s20.i=%00101011011010111100000110010000
;Global s21.i=%11000011000101100011000100001101
;Global s22.i=%10111111011110101100011101000111
;Global s23.i=%01110111100011111010000000100001
;Global s24.i=%11000111010011001101000000010110
;Global s25.i=%01100101000000001100000100001111
;Global s26.i=%11010111101110001000000011100011
;Global s27.i=%11010010011101010110101111000001
;Global s28.i=%11101010100111100101110001011100
;Global s29.i=%11101010011111011100000110100001
;Global s30.i=%00010000101111001011100011101000
;Global s31.i=%00110101000111001001111000100111
;Global s32.i=%01010010011111100100000110001111
;Global s1.i=%10110100001100011001100000001010
Global s1=0
;Global s2.i=%11000100101111000110001011000001
Global s2=0
;Global s3.i=%10001000101010101101110010110000
Global s3=0
;Global s4.i=%11001000101110110011001100110101
Global s4=0
;Global s5.i=%00011001110101010000110001100100
Global s5=0
;Global s6.i=%10111001001111010100000110110010
Global s6=0
;Global s7.i=%10010110111111001111001100110001
Global s7=0
;Global s8.i=%11100001011001100011011011010000
Global s8=0
;Global s9.i=%10001110010101100001001001000100
Global s9=0
;Global s10.i=%10111010011101011110101111101000
Global s10=0
;Global s11.i=%00011100100111000101101101100110
Global s11=0
;Global s12.i=%01110000001100110101001000010100
Global s12=0
;Global s13.i=%11001001111011000100111110010001
Global s13=0
;Global s14.i=%01010001011100000011100111011110
Global s14=0
;Global s15.i=%01010011100001010001011100010110
Global s15=0
Global s16=0
Global s17=0
Global s18=0
Global s19=0
Global s20=0
Global s21=0
Global s22=0
Global s23=0
Global s24=0
Global s25=0
Global s26=0
Global s27=0
Global s28=0
Global s29=0
Global s30=0
Global s31=0
Global s32=%110010100001
Goto LOOP
ElseIf c=0 And unity_found=1
PrintN(Str(cnt))
PrintN("Done!!!")
Debug "start"
Debug Right(Bin(s1),32)
Debug Right(Bin(s2),32)
Debug Right(Bin(s3),32)
Debug Right(Bin(s4),32)
Debug Right(Bin(s5),32)
Debug Right(Bin(s6),32)
Debug Right(Bin(s7),32)
Debug Right(Bin(s8),32)
Debug Right(Bin(s9),32)
Debug Right(Bin(s10),32)
Debug Right(Bin(s11),32)
Debug Right(Bin(s12),32)
Debug Right(Bin(s13),32)
Debug Right(Bin(s14),32)
Debug Right(Bin(s15),32)
Debug Right(Bin(s16),32)
Debug Right(Bin(s17),32)
Debug Right(Bin(s18),32)
Debug Right(Bin(s19),32)
Debug Right(Bin(s20),32)
Debug Right(Bin(s21),32)
Debug Right(Bin(s22),32)
Debug Right(Bin(s23),32)
Debug Right(Bin(s24),32)
Debug Right(Bin(s25),32)
Debug Right(Bin(s26),32)
Debug Right(Bin(s27),32)
Debug Right(Bin(s28),32)
Debug Right(Bin(s29),32)
Debug Right(Bin(s30),32)
Debug Right(Bin(s31),32)
Debug Right(Bin(s32),32)
Input()
EndIf
End
Last edited by alokdube on Thu Aug 18, 2016 11:58 am, edited 5 times in total.
-
Rook Zimbabwe
- Addict
- Posts: 4326
- Joined: Tue Jan 02, 2007 8:16 pm
- Location: Cypress TX
- Contact:
Re: an observation
Whoa!!! That is gonna take me a while to read and parse!!!
Re: an observation
The first response to the algo above for the listed values is d=413, which too works as the decryption key
Note that any "something" and d, that satisifies
k.something+1=ed
is a possible solution because ed is congruent to 1 mod phi(pq) -- pq being product of 2 primes i.e k.something is congruent to 1 mod phi(pq)
It is a much smaller decryptor than 2753 as at:
https://en.wikipedia.org/wiki/RSA_(cryp ... m)#Example
Basically we use the right shift method (computing (2^ something -1) mod m) =0 to find "something, then compute k(something)+1 = ed and use euclidian to find d or k, depending on whichever one is assumed)
__________________________________________________
URL tags added
18.08.2016
RSBasic
Note that any "something" and d, that satisifies
k.something+1=ed
is a possible solution because ed is congruent to 1 mod phi(pq) -- pq being product of 2 primes i.e k.something is congruent to 1 mod phi(pq)
It is a much smaller decryptor than 2753 as at:
https://en.wikipedia.org/wiki/RSA_(cryp ... m)#Example
Basically we use the right shift method (computing (2^ something -1) mod m) =0 to find "something, then compute k(something)+1 = ed and use euclidian to find d or k, depending on whichever one is assumed)
__________________________________________________
URL tags added
18.08.2016
RSBasic
Last edited by alokdube on Thu Oct 27, 2016 1:53 pm, edited 1 time in total.
Re: an observation
The point is that "d" is much easier to compute using the right shift method than computing "k"
"Something " will be LCM of p-1,q-1 ; obviously.
But the objective is to find "d" not p and q
"Something " will be LCM of p-1,q-1 ; obviously.
But the objective is to find "d" not p and q
Last edited by alokdube on Mon Oct 16, 2017 6:19 am, edited 1 time in total.
Re: an observation
Or it is just a bad encryptor in this case, normal ones take a value of "d" as the same number of digits as "m"
Re: an observation
The wiki has been updated to consider "something" as lcm (p-1)(q-1) or the reduced totient lcm (p-1)(q-1) and quotes a lower decryptor now "413"
Re: an observation
Another option is to use
Message^(p+q) mod m = Message^(m+1) mod m
We know p+q is at least 2.sqrt(m)
I.e. the smallest sum of two numbers given their product is when each is equal.
Example p=k.sqrt (m), q=sqrt (m)/k , k is any number and product is m
So p+q = (k^2 +1)/k .sqrt (m)
Minimum when k=1
We also know p+q cannot be more than a 513 bit number is p and q are 512 bits each
We can <<0 to compute (right shift)
2^(p+q) from 2.sqrt (m) till result is 2^(m+1) mod m
We can rewrite it as
Phi() + r = m+1 -2 sqrt(m). , Or round sqrt(m) to nearest int.
Find r where the LHS mod m = RHS mod m
Message^(p+q) mod m = Message^(m+1) mod m
We know p+q is at least 2.sqrt(m)
I.e. the smallest sum of two numbers given their product is when each is equal.
Example p=k.sqrt (m), q=sqrt (m)/k , k is any number and product is m
So p+q = (k^2 +1)/k .sqrt (m)
Minimum when k=1
We also know p+q cannot be more than a 513 bit number is p and q are 512 bits each
We can <<0 to compute (right shift)
2^(p+q) from 2.sqrt (m) till result is 2^(m+1) mod m
We can rewrite it as
Phi() + r = m+1 -2 sqrt(m). , Or round sqrt(m) to nearest int.
Find r where the LHS mod m = RHS mod m