From: pcw@access.digex.net (Peter Wayner)
Date: Sun, 28 Jan 1996 22:20:35 +0800
To: cypherpunks@toad.com
Subject: SDTI Patent (was "Concryption" patent)
Message-ID: <ad3094f2000210042466@[199.125.128.5]>
MIME-Version: 1.0
Content-Type: text/plain



Here are the Claims to the "Concryption" patent (5,479,512) that
was just issued. I've annotated the claims with thoughts about
how they shouldn't apply. For those who don't know patent law,
the system is very heirarchical. For instance claim 1 here is
known as a base claim. Claim 2 is dependent on claim 1.

I believe that Claim 1 would be ruled invalid because of the
prior art contained in my Cryptologia article, "A Redundancy
Reducing Cipher" published in May 88. The journal is found in
many university libraries so I don't think there should be any
argument about the nature of publication.

The article describes how to encipher text by permuting a
Huffman tree used to compress data. The idea was to add some
noise to the compression phase of any encryption. Huffman
compression works by building a big binary tree. The characters
are held in the leaves of the tree. The code for a particular
character is specified by the path from the root to the leaf.
Ordinarily, the left branch is given a 0 and the right branch is
specified by a 1. This addressing remains fixed throughout the
compression. I suggested flipping these addressing bits at some
pseudorandomly determined interval. The purpose of the paper was
to do compression and encryption at the same time.

For that reason, I believe the paper reads directly against
Claim 1, a claim that I also believe is overly broad.  The rest
of the claims seem obvious to me because they borrow well-known
techniques from well-known ciphers like DES. "Obviousness" is a
really non-obvious detail in patent law. Essentially, an idea is
not patentable if the idea is "obvious" to one practiced in the
art. Naturally, this is very hard to define and it depends upon
plenty of case law. In my mind, the only novelty is their
integration with claim 1. I don't know enough about
"obviousness" in this case, but I wouldn't be surprised if the
entire patent failed to hold up under scrutiny.

-Peter Wayner


>CLAIMS: What is claimed is:
>
>   1. A method for utilizing a data processor to change the
>form of data
>comprising the steps of:
>
>   a) obtaining the data at the processor in clear form;
>
>   b) obtaining an encryption key at the processor;
>
>   c) the processor performing a multi-step compression
>operation on said
>clear-form data;
>
>   d) the processor automatically utilizing said encryption key
>in conjunction
>with the results as directly generated by the processor for a
>selected step of
>said compression operation in performing an encryption
>operation, the
>compression steps of step (c) and the encryption step of step
>(d) being
>integrated to be performed as parts of a single operation; and
>
>   e) the processor outputting the resulting compressed and
>encrypted version
>of the clear-form data.
>
>   2. A method as claimed in claim 1 wherein step (e) includes
>the step, of
>storing the resulting compressed and encrypted data in memory.

This should be obvious to anyone skilled in the art of
programming a computer.
>
>   3. A method as claimed in claim 1 wherein step (e) includes
>the step of
>transmitting the resulting compressed and encrypted data.

This should be obvious to anyone skilled in the art of
programming a computer.

>
>   4. A method as claimed in claim 1 wherein said encryption
>key is a code
>derived from a token.

This should be obvious to anyone skilled in the art of
programming a computer.
>
>   5. A method as claimed in claim 4 wherein the code derived
>from a token is
>a one-time nonpredictable code.

I'm not sure what a one-time, unpredictably code. But it would
help if both sides could have access to it. This should be
obvious to anyone skilled in the art of programming a computer.

>
>   6. A method as claimed in claim 1 wherein step (d) includes
>the steps
>performed by the processor of dividing the results of the
>selected step of the
>compression operation into a plurality of segments, selecting
>an encryption
>key for each segment and performing an encryption operation for
>each segment
>utilizing the corresponding encryption key.

This should be obvious to anyone skilled in the art of creating
a crypto
system. Block ciphers are very common. DES is well known.

>
>   7. A method as claimed in claim 6 wherein the step of
>selecting an
>encryption key includes the step of processing the obtained
>encryption key to
>form a separate encryption key for each of the plurality of
>segments.

Key permutation is also well-known. One form of DES uses the
result from the previous block to change the key for the next
block.
>
>   8. A method as claimed in claim 6 wherein the step of
>selecting an
>encryption key includes the step of utilizing the same
>encryption key for all
>segments.

Big deal.
>
>   9. A method as claimed in claim 1 wherein step (d) includes
>the steps
>performed by the processor of dividing the results of the
>selected step of the
>compression operation into a plurality of segments, utilizing
>the obtained
>encryption key to perform an encryption operation for a first
>of said
>segments, and utilizing a selected function of at least a
>portion of the
>encryption operation for a given segment as the encryption key
>for performing
>an encryption operation on a succeeding segment.

Should be obvious for the usual reasons. DES did cipher block
chaining.
>
>   10. A method as claimed in claim 9 wherein the data is text
>and wherein a
>segment is N lines of such text, where N is an integer.

Big deal.
>
>   11. A method as claimed in claim 1 wherein the encryption
>operation
>includes the step of the processor performing an exclusive
>ORing operation
>with the encryption key and the results of the selected step.

Should be obvious. The method is used in other systems.
>
>   12. A method as claimed in claim 1 wherein step (b) includes
>the step of
>forming the encryption key by exclusive ORing a password for a
>system user
>with a code derived from a token in the possession of the user.
>
>   13. A method as claimed in claim 1 wherein step (c) includes
>the step of
>the processor performing an initial run-length encoding
>operation on the
>
>clear-form data and
>
>   wherein step (d) is performed on the results of the
>run-length encoding
>step.
>
>   14. A method as claimed in claim 1 wherein step (d) is
>performed on at
>least one element used in a compression step.
>
>   15. A method as claimed in claim 14 wherein the element on
>which encryption
>is performed is a table used in performing a compression step.
>
>   16. A method as claimed in claim 1 including the step of
>restoring the data
>to clear form for utilization, said restoring step including
>the steps of
>performing at least one decompression operation and at least
>one deencryption
>operation, said decompression and deencryption steps being
>performed in
>reverse order to the performance of steps (c) and (d).
>
>   17. A method for utilizing a data processor to concrypt data
>comprising the
>steps of:
>
>   the processor obtaining the data in clear form;
>
>   the processor performing a concryption operation on the
>clear data, said
>concryption operation including at least one compression step
>and at least one
>encryption step automatically performed in a selected sequence
>as an integral
>operation; and
>
>   the processor outputting the resulting concrypted data.
>
>   18. A method as claimed in claim 17 including the step
>performed at a data
>processor of deconcrypting the concrypted data to permit use
>thereof in clear
>form, the deconcrypting step including at least one
>decompression step and at
>least one deencryption step performed automatically in a
>sequence which is
>substantially the reverse of said selected sequence.
>
>   19. A method as claimed in claim 17 wherein an encryption
>step is performed
>on the results of at least one stage of a compression step.
>
>   20. A method as claimed in claim 17 wherein an encryption
>step is performed
>on at least one element used in a compression step.


The rest of these are just apparatus claims that seem to repeat
the earlier, more abstract "method" claims in different form.
Patent law has traditionally distinguished between an idea for
doing something, the "method", and the machines that actually do
it, "the apparatus." I didn't see anything new here.
>
>   21. Apparatus for utilizing a data processor to change the
>form of data
>comprising:
>
>   means for obtaining the data at the processor in clear form;
>
>   means for obtaining an encryption key at the processor;
>
>   means for performing at the processor a multi-step
>compression operation on
>said clear-form data;
>
>   means at the processor for automatically utilizing said
>encryption key in
>conjunction with the results as directly generated by the
>processor for a
>selected step of said compression operation in performing an
>encryption
>operation, the compression performed by the compression means
>and the
>encryption performed by the encryption means being integrated
>to be performed
>as parts of
>
>the same operations; and
>
>   means at the processor for outputting the resulting
>compressed and
>encrypted version of the clear-form data.
>
>   22. Apparatus as claimed in claim 21 wherein the means for
>performing an
>encryption operation includes means at the processor for
>dividing the results
>of the selected step of the compression operation into a
>plurality of
>segments, and means for performing an encryption operation for
>each segment
>utilizing the corresponding encryption key.
>
>   23. Apparatus as claimed in claim 22 wherein the means for
>selecting an
>encryption key includes means for processing the obtained
>encryption key to
>form a separate encryption key for each of the plurality of
>segments.
>
>   24. Apparatus as claimed in claim 21 wherein the means for
>performing an
>encryption operation includes means at the processor for
>dividing the results
>of the selected step of the compression operation into a
>plurality of
>segments, means for utilizing the obtained encryption key to
>perform an
>encryption operation for a first of said segments, and means
>for utilizing a
>selected function of at least a portion of the encryption
>operation for a
>given segment as the encryption key for performing an
>encryption operation on
>a succeeding segment.
>
>   25. Apparatus as claimed in claim 21 wherein the means for
>performing an
>encryption operation includes means at the processor for
>performing an
>exclusive ORing operation with the encryption key and the
>results of the
>selected step.
>
>   26. Apparatus as claimed in claim 21 wherein the means for
>performing a
>multistep compression operation includes means at the processor
>for performing
>an initial run-length encoding operation on the clear-form
>data; and
>
>   wherein the encryption operation is performed on the results
>of the run-
>length encoding operation.
>
>   27. Apparatus as claimed in claim 21 including means for
>restoring the data
>to clear form for utilization, said means for restoring
>including means for
>performing at least one decompression operation and at least
>one deencryption
>operation, said decompression and deencryption operations being
>performed in
>reverse order to the performance of compression and encryption
>by said means
>for compressing and said means for encrypting, respectively.
>
>   28. Apparatus for utilizing a data processor to concrypt
>data comprising:
>
>   means for obtaining the data at the processor in clear form;
>
>   means for performing a concryption operation at the
>processor on the clear
>data, said concryption operation including means for performing
>at least one
>compression step and means for performing at least one
>encryption step, said
>compression and encryption steps being automatically performed
>in a selected
>sequence as an integrated operation; and    means for the
>processor outputting
>the resulting concrypted data.
>
>   29. Apparatus as claimed in claim 28 including means at a
>data processor
>for deconcrypting the concrypted data to permit use thereof in
>clear form, the
>means for deconcrypting including means for performing at least
>one
>decompression step and means for performing at least one
>deencryption step;
>the decompression and deencryption steps being performed
>automatically in a
>sequence which is substantially the reverse of said selected
>sequence.
>

<< end of forwarded material >>