[squeak-dev] SqueakElib project

Robert Withers robert.w.withers at gmail.com
Sun Dec 6 02:59:07 UTC 2015



On 12/05/2015 09:30 PM, Robert Withers wrote:
> I could briefly explain and put creation of new SecureSession 
> architecture sketch on my medium stack. I have a few diagrams already 
> which I will add, but none of this new SecureSession design. This is 
> done so please check that page.
>
> Reed Solomon encoding:
> Using Reed-Solomon encoding for Forward Error Correction is used is 
> satellite communications. Other lossy communications probably uses 
> this or something similar. By interleaving RS encoded blocks, you 
> quadruple the contiguous bytes that can be corrupted and still 
> recovered. My use here will specify 4 interleaved blocks. So the 
> encoding is really an RS encoding of 4 blocks and then interleaving them.
>
> Note that QR Codes are using RS encoding.
>
> RS encoding uses a GaloisField, or a finite field. This is a system of 
> polynomials that are multiplied, divided, inversed and added to 
> transform the data into code (as in coded data). The Galois Field is 
> initialized with a primitive polynomial that sets the symbol size of 
> data, symbol size of code and the number of errors that is still 
> recoverable. Thus there are many different primitive polynomials as 
> there are uses of RS encoding. Note that the symbol size tends to be a 
> nibble. I use 3 different sized primitive polynomials, so I have 
> different sized blocks depending on the size of the payload to be 
> fragmented and encoded, in groups of 4 interleaved blocks.
>
> The easiest RS encoding to look at has 9 data symbols, 15 code symbols 
> and can handle 3 symbol errors. Considering that these 15 
> symbols/block will be interleaved with 3 other blocks, we are talking 
> about 60 symbols, or 30 bytes coded. This is 18 bytes of data. As they 
> are interleaved with 3 errors per block permissible, that is 12 
> contiguous bytes can be corrupted and the msg recovered.

I need to make a correction to what I've said, that is 3 symbol errors 
per coded block, or 3 nibbles. So the contiguous space that can be 
recovered is 6 bytes coded, out of 30 bytes. Higher degree primitive 
polynomials have different sizes for data, code, errors and so a larger 
encoding with 4-block interleaving may result in hundreds of contiguous 
bytes being resilient. I do think it is in the neighborhood of 10-20% of 
the coded message is recoverable, generally.

Robert
>
> The interleaving takes the first byte from each of 4 blocks, then the 
> second...
>
> [byteA1, byteB1, byteC1, byteD1, byteA2, byteB2, ...]
>
> I hope this helps! I'll add it to the project wiki.
>
> Robert
>
>
>
> On 12/05/2015 08:34 PM, Ben Coman wrote:
>> This is interesting, "error correction through Reed Solomon encoding"
>> but its not clear how its used.  Maybe a sketch of the architecture
>> would be useful.
>> cheers -ben
>>
>> On Fri, Dec 4, 2015 at 9:31 PM, Robert Withers
>> <robert.w.withers at gmail.com> wrote:
>>> Good morning,
>>>
>>> Here is a brief writeup of the SqueakElib project and its direction.
>>>
>>> https://github.com/SqueakCryptographySquad/Cryptography-Common/wiki/SqueakElib. 
>>>
>>>
>>> All new squad members welcome.
>>>
>>> Regards,
>>> Robert
>>>
>



More information about the Squeak-dev mailing list