Method and apparatus for a robust high-speed cryptosystem
First Claim
Patent Images
1. A cryptographic method comprising the steps of:
- providing a plurality of key section construction methods;
deriving a decryption key including a decryption key set of identifiables logically segregated into sections, each said section generated by one of a plurality of construction methods and said segregation is kept secret;
deriving from said decryption key an encryption key, each section of said decryption key set is transformed to a corresponding section of said encryption key set and at least two said sections are transformed under different transformation methods, and previously generated and transformed sections are transformed together with the currently generated section;
accepting a message in the form of an input sequence of integers;
converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector;
generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector;
accepting a ciphertext; and
decrypting said ciphertext to recover said message.
0 Assignments
0 Petitions
Accused Products
Abstract
A cryptographic information and communication system of the knapsack type characterized by secret logical segregation of the key sets into sections by different construction methods, where different transformations are applied to different sections, and characterized by non-constant number of subset sum solutions to ciphertext, where resolution protocols are employed when necessary to resolve non-unique subset sum solutions at the decryptor.
60 Citations
17 Claims
-
1. A cryptographic method comprising the steps of:
-
providing a plurality of key section construction methods; deriving a decryption key including a decryption key set of identifiables logically segregated into sections, each said section generated by one of a plurality of construction methods and said segregation is kept secret; deriving from said decryption key an encryption key, each section of said decryption key set is transformed to a corresponding section of said encryption key set and at least two said sections are transformed under different transformation methods, and previously generated and transformed sections are transformed together with the currently generated section; accepting a message in the form of an input sequence of integers; converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector; generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector; accepting a ciphertext; and decrypting said ciphertext to recover said message. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A cryptographic method which securely communicates data from a first party S to a second party R comprising the steps of:
deriving cryptographic keys at party R comprising; providing a plurality of key section construction methods; deriving a decryption key to be kept secret at party R including a decryption key set of identifiables logically segregated into sections, each section generated by one of a plurality of construction methods and said segregation is kept secret; deriving from said decryption key an encryption key, each section of said decryption key set is transformed to a corresponding section of said encryption key set, and at least two sections are transformed under different transformation methods, and previously generated and transformed sections are transformed together with the currently generated section; distributing said encryption key from party R to party S; receiving said encryption key at party S; generating ciphertext at party S comprising; accepting a message in the form of an input sequence of integers; converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector; and generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector; transmitting said ciphertext from party S to party R over a communication channel; receiving said ciphertext at party R; and decrypting said ciphertext at party R to recover said message. - View Dependent Claims (11)
-
12. A cryptographic method comprising the steps of:
-
deriving a decryption key by generating a decryption key set of identifiables logically segregated into k>
1 sections;
##EQU5## and a decryption fuzzy residue set with corresponding sections to Kd;
space="preserve" listing-type="equation">G=G.sub.1 ∪
G.sub.2 ∪
. . . ∪
G.sub.kand a wrinkling set with corresponding sections to Kd ;
space="preserve" listing-type="equation">B=B.sub.1 ∪
B.sub.2 ∪
. . . ∪
B.sub.kwhere Kd, G and B are to be kept secret and each section i, for 1≦
i≦
k is Kd is generated by at least one of the following constructions;1) standard 2) submerged 3) wrinkled 4) individually mapped 5) multiply mapped and for a submerged section i di,j =2h(j-1) *mi, for 1≦
j≦
zi, where subscript i in ml is defined to be;
i.tbd.i, 0.tbd.i-1, zi-1and for a wrinkled section i σ
=sum(η
.sub.θ
* |θ
|)+rdi,j =σ
+Ψ
i-1 (bi,j), for 1≦
j≦
ziand for a section of any of the other types;
##EQU6## where r is a non-zero positive ranged random number, η
.sub.θ
is the maximum applicable multiple of θ
ε
Θ
i-1, and Θ
i is defined to be ##EQU7## where Cu,v ({μ
1, μ
2, . . . , μ
n })={Cu,v (μ
1), Cu,v (μ
2), . . . , Cu,v (μ
n)} denotes a complementation function for the construction of the entire encryption key and Cu,v (μ
), for any number μ
, is either defined to be;
##EQU8## and gε
G is a ranged random number;
deriving fuzzy residue mapping FM( ), whereby elements of said key sets are associated with elements of said fuzzy residue set, and FM( ), for a section i having at least one element individually mapped, is defined to be;
##EQU9## satisfying IM(μ
-1)=(μ
-1)*di,j <
IM(μ
)+μ
*di,j <
IM(μ
+1)+(μ
+1)*di,j, where X=X1 ∪
X2 ∪
. . . ∪
Xk is a set of integers in the ranges of [0, 2h) input to FM( ) and xi,j corresponds to ei,j and IM(xi,j) equals the value of applied residues mapped to by xi,j,and FM( ), for a section i having elements multiply mapped, is defined to be;
space="preserve" listing-type="equation">FM(X)=FM(X.sub.1 ∪
X.sub.2 ∪
. . . ∪
X.sub.k)=FM(X.sub.1)+FM(X.sub.2)+ . . . +FM(X.sub.k)where FM(Xi)=SM(Σ
IM(xi,j)) for 1≦
j≦
zi and IM(xi,j) equals xi,j if ei,j is mapped and equals zero otherwise, and SM(μ
) returns α
*gi,j for some integer α
corresponding to the value of μ
satisfying;
space="preserve" listing-type="equation">SM(μ
-1)<
SM(μ
)<
SM(μ
+1);deriving from said decryption key an encryption key θ
k, inheriting said fuzzy residue mapping;generating ciphertext comprising; accepting a message in the form of an input sequence of integers in the range of [0, 2h); converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector X having the same dimensions as said key vector; and generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector defined by;
space="preserve" listing-type="equation">γ
=K.sub.e ×
X+FM(X)if fuzzy residues have been generated for said encryption key, and defined by;
space="preserve" listing-type="equation">γ
=K.sub.e ×
Xotherwise; obtaining a decryption key; decrypting said ciphertext to recover said message via decrypting each of the ciphertext block of said ciphertext, and corresponding to a standard section i of said encryption key set, the decryption is carried out according to;
##EQU10## and after obtaining all yi,j for 1≦
j≦
zi, is adjusted by;
##EQU11## and corresponding to a submerged section i, the decryption is carried out according to;
##EQU12## where Ω
is the set of elements in θ
i-1 that are tranformed from said decryption key set and Y'"'"' is the decrypted {y1,1, y1,2, . . . yi-1,μ
}, where μ
=z1-1,and corresponding to a wrinkled section i, the decryption is carried out according to;
##EQU13## where b'"'"'i,j is the decoded multiple of identifiable bi,j contained in γ
'"'"', and after obtaining qi, γ
'"'"' is adjusted by;
γ
'"'"'<
γ
'"'"'-qi *di,1.and corresponding to an individually mapped section i, the decryption is carried out, for j=zi down to 1, according to;
space="preserve" listing-type="equation">γ
'"'"'<
Γ
.sub.i.sup.-1 (γ
'"'"')
space="preserve" listing-type="equation">y.sub.i,j <
q,satisfying;
space="preserve" listing-type="equation">FM(q-1)+(q-1)*d.sub.i,j ≦
FM(q)+q*d.sub.i,j <
FM(q+1)+(q+1)*d.sub.i,jand after obtaining each yi,j, γ
'"'"' is adjusted by;
space="preserve" listing-type="equation">γ
'"'"'<
γ
'"'"'-FM(y.sub.i,j)-y.sub.i,j *d.sub.i,jand corresponding to a multiply mapped section i, the decryption is carried out, for j=zi down to 1, according to;
space="preserve" listing-type="equation">γ
'"'"'<
Γ
.sub.i.sup.-1 (γ
'"'"')
space="preserve" listing-type="equation">y.sub.i,j <
q, satisfying;
space="preserve" listing-type="equation">FM(q)+q*d.sub.i,j ≦
γ
'"'"'and after obtaining each yi,j, γ
'"'"' is adjusted by;
##EQU14## where for the decryption of section k, the last generated section of the decryption key set, γ
'"'"' equals the ciphertext γ
to be decrypted and
space="preserve" listing-type="equation">Γ
.sub.i.sup.-1 =Γ
.sub.i,1.sup.-1 °
Γ
.sub.i,2.sup.-1 °
. . . °
Γ
.sub.i,t.sbsb.i.sup.-1
space="preserve" listing-type="equation">Γ
.sub.u,v.sup.- (μ
)=C.sub.u,v.sup.-1 ((w.sub.u,v.sup.-1 *μ
)Ξ
m.sub.u,v)Cu,v-1 denotes the reverse of Cu,v, where Cu,v-1 (μ
), for any number μ
, is defined as;
##EQU15##
-
-
13. A cryptographic system comprising:
- means for providing a plurality of key section construction methods;
means for deriving a decryption key including a decryption key set of identifiables logically segregated into sections, each said section generated by one of a plurality of construction methods and said segregation is kept secret; means for deriving from said decryption key an encryption key, each section of said decryption key set is transformed to a corresponding section of said encryption key set and at least two said sections are transformed under different transformation methods, and previously generated and transformed sections are transformed together with the currently generated section; means for accepting a message in the form of an input sequence of integers; means for converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector; means for generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector. means for accepting a ciphertext; and means for decrypting said ciphertext to recover said message. - View Dependent Claims (14)
- means for providing a plurality of key section construction methods;
-
15. A cryptographic system which securely communicates data from a first party S to a second party R comprising:
-
means for deriving cryptographic keys at party R comprising; means for providing a plurality of key section construction methods; means for deriving a decryption key to be kept secret at party R including a decryption key set of identifiables logically segregated into sections, each section generated by one of a plurality of construction methods and said segregation is kept secret; means for deriving from said decryption key an encryption key, each section of said decryption key set is transformed to a corresponding section of said encryption key set, and at least two sections are transformed under different transformation methods, and previously generated and transformed sections are transformed together with the currently generated section; means for distributing said encryption key from party R to party S; means for obtaining said encryption key at party S; means for generating ciphertext at party S comprising; means for accepting a message in the form of an input sequence of integers; means for converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector; and means for generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector; means for transmitting said ciphertext from party S to party R over a communication channel; means for receiving said ciphertext at party R; and means for decrypting said ciphertext at party R to recover said message. - View Dependent Claims (16)
-
-
17. A cryptographic system comprising:
-
means for deriving a decryption key by generating a decryption key set of identifiables logically segregated into k>
1 sections;
##EQU16## and a decryption fuzzy residue set G=G1 ∪
G2 ∪
. . . ∪
Gk and a wrinkling set B=B1 ∪
B2 ∪
. . . ∪
Bk with sections corresponding to those in Kd, wherein Kd, G and B are to be kept secret and each section i, for 1≦
i≦
k of Kd is generated by at least one of the following constructions;1) standard 2) submerged 3) wrinkled 4) individually mapped 5) multiply mapped and for a submerged section i di,j =2h(j-1) *mi, for 1≦
j≦
zi, where subscript i and mi is defined to be;
i.tbd.i, 0.tbd.i-1, zi-1and for a wrinkled section i σ
=sum(η
.sub.θ
*|θ
|)+rdi,j =σ
+Ψ
i-1 (bi,j), for 1≦
j≦
ziand for a section of any of the other types;
##EQU17## where r is a non-zero positive ranged random number, η
.sub.θ
is the maximum applicable multiple of θ
ε
Θ
i-1, and Θ
i is defined to be ##EQU18## where Cu,v {μ
1, μ
2, . . . , μ
n })={Cu,v (μ
1), C.sub.μ
,ν
(μ
2), . . . , Cu,v(μ
n)} denotes a complementation function for the construction of the entire encryption key and Cu,v (μ
), for any number μ
, is either defined to be;
##EQU19## and g ε
G is a ranged random number;
means for deriving fuzzy residue mapping FM( ), whereby elements of said key sets are associated with elements of said fuzzy residue set, and FM( ), for a section i having at least one element individually mapped, is defined to be;
##EQU20## satisfying IM(μ
-1)+(μ
-1)*di,j <
IM(μ
)+μ
*di,j <
IM(μ
+1)+(μ
+1)*di,j, where X=X1 ∪
X2 ∪
. . . ∪
Xk is a set of integers in the ranges of [0, 2h) input to FM( ) and xi,j corresponds to ei,j and IM(xi,j) equals the value of applied residues mapped to by xi,j,and FM( ), for a section i having elements multiply mapped, is defined to be;
FM(X)=FM(X1 ∪
X2 ∪
. . . ∪
Xk)=FM(X1)+FM(X2)+ . . . +FM(Xk) where FM(Xi)=SM(Σ
IM(xi,j)) for 1≦
j≦
zi and IM(xi,j) equals xi,j if ei,j is mapped and equals zero otherwise, and SM(μ
) returns α
*gi,1 for some integer α
corresponding to the value of μ
satisfying;
space="preserve" listing-type="equation">SM(μ
-1)<
SM(μ
)<
SM(∥
+1);means for deriving from said decryption key an encryption key Θ
k, inheriting said fuzzy residue mapping,means for obtaining an encryption key; means for generating ciphertext comprising; means for accepting a message in the form of an input sequence of integers in the range of [0, 2h); means for converting said encryption key set to a key vector and converting said input sequence of integers to at least one data vector having the same dimensions as said key vector; and means for generating ciphertext by computation that includes calculating the inner product of each of said data vectors with said key vector defined by;
space="preserve" listing-type="equation">γ
=K.sub.e ×
X+FM(X)if fuzzy residues have been generated for said encryption key, and defined by;
space="preserve" listing-type="equation">γ
=K.sub.e ×
Xotherwise. means for accepting a ciphertext; means for obtaining a decryption key corresponding to said encryption key; means for decrypting said ciphertext to recover said message via decrypting each of the blocks of said ciphertext, and corresponding to a standard section i of said encryption key set, the decryption is carried out according to;
##EQU21## and after obtaining all yi,j for 1≦
j≦
zi, γ
'"'"' is adjusted by;
##EQU22## and corresponding to a submerged section i, the decryption is carried out according to;
##EQU23## where Ω
is the set of element in Θ
i-1 that are transformed from said decryption key set and Y'"'"' is the decrypted {y1,1, y1,2, . . . , yi-1,u }, where u=zi-1,and corresponding to a wrinkled section i, the decryption is carried out according to;
##EQU24## where b'"'"'i,j is decoded multiple of identifiable bi,j contained in γ
'"'"', and after obtaining qi, γ
'"'"' is adjusted by;
γ
'"'"'<
γ
'"'"'-qi *di,1.and corresponding to an individually mapped section i, the decryption is carried out, for j=z1 down to 1, according to;
space="preserve" listing-type="equation">γ
'"'"'<
Γ
.sub.i.sup.-1 (γ
'"'"')
space="preserve" listing-type="equation">y.sub.i,j <
q, satisfying;
space="preserve" listing-type="equation">FM(q-1)+(q-1)*d.sub.i,j ≦
FM(q)+q*d.sub.i,j <
FM(q+1)+(q+1)*d.sub.i,jand after obtaining each yi,j, γ
'"'"' is adjusted by;
space="preserve" listing-type="equation">γ
'"'"'<
γ
'"'"'-y.sub.i,j *d.sub.i,j -FM(y.sub.i,j)and corresponding to a multiply mapped section i, the decryption is carried out, for j=zi down to 1, according to;
space="preserve" listing-type="equation">γ
'"'"'<
Γ
.sub.i.sup.-1 (γ
'"'"')
space="preserve" listing-type="equation">y.sub.i,j <
q, for the largest q satisfying;
space="preserve" listing-type="equation">FM(q)+q*d.sub.i,j ≦
γ
'"'"'and after obtaining each yi,j, γ
'"'"' is adjusted by;
##EQU25## where fore the decryption of section k, the last generated section of the decryption key set, γ
'"'"' equals the ciphertext γ
to be decrypted and
space="preserve" listing-type="equation">Γ
.sub.i.sup.-1 =Γ
.sub.i,1.sup.-1 °
Γ
.sub.i,2.sup.-1 °
. . . °
Γ
.sub.i,y.sbsb.i
space="preserve" listing-type="equation">Γ
.sub.u,v.sup.- (μ
)=C.sub.u,v.sup.-1 ((w.sub.u,v.sup.-1 *μ
)Ξ
m.sub.u,v)Cu,v-1 denotes the reverse of Cu,v, where Cu,v-1 (μ
), for any number μ
, is defined as;
##EQU26##
-
Specification