臺灣博碩士論文加值系統

本篇論文所研究的重點是偵測可寫一次光碟的竄改。就我們所知，數位簽章可以保證資料的完整性，但是有兩點數位簽章是無法保證的：第一、當一位惡意竄改者擁有無限的硬體和時間，我們就不能保證系統無法被破壞，第二、簽章時需要一把金鑰，當一位惡意竄改者獲得這把金鑰後，則使用數位簽章就無法有效的偵測惡意竄改者對可寫一次光碟的竄改。另外使用數位簽章需要用到密碼技術，而本篇論文則是利用編碼的方法適當的使用t個錯誤更正與所有單向錯誤偵測碼(t-EC/AUED碼)來達到保護可寫一次光碟資料完整的目的。可寫一次光碟有兩個重要的特性。第一：可寫一次光碟所發生的錯誤是非對稱的(也就是只有 “0”會錯成 “1”)。第二：在可寫一次光碟中使用(d,k)-RLL限制碼(至少d 個連續 “0”是為了防止ISI，至多k 個連續 “0”則是可以達到同步的目的)。
本篇論文我們提出新的光碟編碼保護技術來替代數位簽章，以達到光碟在干擾環境下也能保護光碟資料的完整性。簡短敘述如下，我們提出利用非系統格式的t-EC/AUED碼代替[3]中原有系統格式的t-EC/AUED碼以建立檢測位元。另外，我們也提出直接編成具有t-EC/AUED錯誤檢測能力的 (d,k,k-1,k-1)-RLL限制碼來建立檢測位元，此種方法分為系統格式及非系統格式。我們的方法相較於過去利用t-EC/AUED碼當作檢測位元的方法皆減少了檢測位元的長度，能有較好的碼率。最後我們定義了一種新類型的光碟防竄改編碼，將竄改能力由 AUED 減為檢測有限個錯誤，如此可得到較小的檢測位元長度。
本篇論文不使用數位簽章密碼技術，這種基於 “計算量不可能”的演算法來得到可寫一次光碟資料的完整性，而是使用編碼技術，因此它可以達到完美的安全性，進而確保可寫一次光碟資料的完整無誤。本篇論文中所提的編碼方法，各具特色技術及應用，期望能將檢測碼長度降低並依照不同需求使用其技術。

In the thesis, we will study the code for detection of tampering in write-once optical disk. As we know, digital signature can be used to ensure data integrity. However the followings cannot be guaranteed. First, when an attacker has infinite hardware and time, we cannot guarantee that he cannot break the system. Second, a key is needed in verification. When an attacker gains physical possession of the key, the approach of protecting optical disk is useless. In addition, using digital signature to protect optical disk from tampering, we must use cryptographic techniques. In the thesis, we use coding approach instead of digital signature to achieve the goal. There are two properties in optical disk. First, the error pattern of optical disk is asymmetric i.e. only “0” can be changed to “1”. Second, the (d, k)-RLL constrained code is used in optical disk. At least “d” consecutive zeros is to avoid ISI, and at most “k” consecutive zeros is to maintain the bit synchronization of system clock.
Here, we propose new coding approaches instead of digital signature for detection of tampering in optical disk. We use nonsystematic t-EC/AUED (t-Error Correcting/All Unidirectional Error Detection) code instead of systematic t-EC/AUED code [3] to construct the check bit. In addition, we also propose a new (d, k, k-1, k-1)–RLL constrained sequence with t-EC/AUED capability to construct the check bit. This method has two types: one is systematic and the other is nonsystematic. All methods improve the length of tail part than the previously code and achieve better code rate. Finally, we define a new class of code with finite tampering detection capability instead of AUED such that we can save the tail part.
We do not use cryptograph technique that is based on “computation infeasible” to ensure data integrity, but use coding approach to achieve perfect secrecy. We can choose the coding approaches according our requirement and application.

1. Introduction 1
1.1 Detect Tampering in Write-Once Optical Disks 2
1.2 Motivation and Contribution of the Thesis 4
1.3 Outline of the Thesis 5
2. Preliminaries and The Previously Coding Approach 6
2.1 Preliminary 6
2.1.1 (d, k)-RLL Constrained Code 6
2.1.2 (d, k, l, r)-RLL Constrained Code 7
2.1.3 Merging of dk and dklr Sequences 9
2.1.4 Nonsystematic t-EC/AUED Code 10
2.1.5 Systematic t-EC/AUED Code Using T1(��),
T2(��) and T3(��) 12
2.2 The Previous Coding Approach 13
3. The Proposed Codes for Detection of Tampering
in Write-Once Optical Disks 18
3.1 Use the Nonsystematic t-EC/AUED Code
to Construct Tail Part in a Noisy Environment 19
3.2 Use the (d, k, l, r)-RLL Constrained Code
with t-EC/AUED Capability to Construct Tail Part
in a Noisy Environment ― Systematic Method 24
3.3 Use the (d, k, l, r)-RLL Constrained Code
with t-EC/AUED Capability to Construct Tail Part
in a Noisy Environment ― Nonsystematic Method 31
4. Tables and Compared Results 39
5. A New Class of Code with Finite Tampering
Detection Capability 45
5.1 (t1, t2, t3)-Code of Tampering Detection
Capability in a Noisy Environment 45
5.2 The Improvement of (t1, t2, t3)-Code 49
6. Conclusions and Future Works 51
6.1 Conclusions 51
6.2 Future Works 52
References 53

[1]Abdel-Ghaffar, K.A.S.; Weber, J.H., “Constructing efficient DC-free runlength-limited block codes for recording channels,” IEEE Trans. on Information Theory, vol. 46, Issue.4, July. 2000.
[2]K.A.S. Abdel-Ghaffar and H.C. Ferreira, “Systematic encoding of thr Varshamov-Tenengol’ts codes and the Constantin–Rao codes,” IEEE Trans. On Information Theory, vol. C-44, pp. 103-108, Jan. 1998.
[3]M. Blaum and J. Bruck, “A coding approach for detection of tampering in write-once optical disks”, IEEE trans. on Computers, vol. C-47, pp.120-125, Jan. l998.
[4]C.N. Yang and C.S. Laih, “Generating functions for asymmetric/unidirectional error correcting and detecting codes,” IEICE Trans. on Funda., vol. C-45, pp. 103-108, Jan. 1997.
[5]C.S. Laih and C.N. Yang, “On the analysis and design of group theoretical t-syEC/AUED codes,” IEEE Trans. on Computers, vol. C-45, pp. 103-108, Jan. 1996.
[6]R. Katti, “A note on SEC/AUED codes,” IEEE Trans. on Computers, vol. C-45, pp.244~246, May 1996.
[7]R. Katti and M Blaum, �AAn improvement on constructions of t-EC/AUED codes,” IEEE Trans. on Computers, vol. C-45, pp.607-608, May l996.
[8]S. Al-Bassam and B. Bose, “Asymmetric/unidirectional error correcting and detecting codes,” IEEE Trans. on Computers, vol. C-43, pp.590-597, May l994.
[9]S. Al-Bassam and B. Bose, “Design of Efficient Balanced Codes,” IEEE Trans. on Computers, vol.43, no.3,pp.362-365,Mar.1994.
[10]M.C. Lin , “Constant weight codes for correcting symmetric codes and detecting unidirectional errors,” IEEE Trans. on Computers, vol. C-42, pp.1294-1302, Nov. 1993.
[11]S. Al-Bassam and B. Bose, “Design of efficient error-correcting balanced codes,” IEEE Trans. on Computers, vol. C-42, pp.1261-1266, Oct. 1993.
[12]B. Bose and S. Al-Bassam, “Byte unidirectional error correcting and detecting codes,” IEEE Trans. on Computers, vol. 41, pp.1601-1606, Dec. l992.
[13]J. Bruck and M. Blaum, “New techniques for constructing EC/AUED codes,” IEEE Trans. on Computers, vol. C-41, pp.1318~1324, Oct. 1992.
[14]D. Nikolos, “Theory and Design of t-Error correcting/d-error detecting (d>t) and all unidirectional error detecting codes,” IEEE Trans. on Computers, vol. C-40, pp. l32-l43, Feb. l99l.
[15]K.A.S. Immink, Coding Techniques for Digital Recorders, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1991.
[16]A.E. BROUWER, JAMES B SHEARER, N.J.A. SLOANE, and WARREN D.SMITH, “A NEW Table of Constant Weight Codes,” IEEE Trans. on Information Theory, vol. 36, NO.6, Nov. 1990.
[17]A.H. Brouwer, J.B. Shearer, N.J.A. Sloane, and W.D. Smith, “A new table of constant weight codes,” IEEE Trans. on Information Theory, vol. IT-36, pp.1334-1380, Nov. 1990.
[18]D.L. Tao, C.R.P. Hartmann, and P.K. Lala, “Systematic random error correcting and all unidirectional error detecting codes,” IEEE Trans. on Computers, vol. C-39, pp. 836-840, June l990.
[19]S. Kundu, “Design of non-symmetric 3syEC/AUED codes of asymptotically optimal order,” Int. Symp. Information. Theory, Jan. 1990.
[20]S. Kundu, “On symmetric error correcting and all unidirectional error detecting codes,” IEEE Trans. on Computers, vol. C-39, pp.752-76l, June l990.
[21]M. Blaum and H. Van Tilborg, “On-t-error correcting/all unidirectional error detecting codes,” IEEE Trans. on Computers, vol.38, pp. l493-l50l, Nov. l989.
[22]T.R.N. Rao and E. Fujiwara, Error Control Coding for Computer Systems, Prentice-Hall, 1989.
[23]D. Nikolos, N. Gaitanis, and G. Philokyprou, “Systematic t-error correcting/all unidirectional error detecting codes,” IEEE Trans. on Computers, vol. C-35, pp. 394-402, May l986.
[24]P.H. Siegel, “Recording codes for digital magnetic storage,” IEEE Trans. on Magnetic, vol. MAG-21, pp.1344-1349, Sep. l985.
[25]E.L. Lesis, “Data integrity in digital optical disks”, IEEE Trans. on Computers, vol. C-33, pp.818-827, Sep. l984.
[26]G. F. M. Beenker and K. A. Schouhamer Immink, “A Generalized Method for Encoding and Decoding Run-Length-Limited Binary Sequences,” IEEE Trans. on Information Theory, vol. 29, NO.5, Sep. 1983.
[27]S. Lin and D.J., Costello, JR., Error Control Coding : Fundamentals and Applications, Prentice-Hall, 1983.
[28]B.Bose and D.K. Pradhan, “Optimal unidirectional error detecting/correcting codes,, IEEE Trans. on Computers, vol. C-31, pp. 564-568, June 1982.
[29]B. Bose and T.R.N. Rao, “Theory of unidirectional error correcting/detecting codes,” IEEE Trans. on Computers, vol. C-3l, pp.52l-530, June l982.
[30]R. Adler, M. Hassner, and J. Moussouris, “Method and apparatus for generating a noiseless sliding block code for a (1, 7) channel with rate 2/3,” U.S. Patent 4,413,251, 1982.
[31]D.K. Pradhan, “A new class of error-correcting/detecting codes for fault tolerant computer applications,” IEEE Trans. on Computers, vol. C-29, pp.47l-48l, June l980.
[32]R.L. Graham and N.J. A. Sloane, “Lower bounds on constant weight codes,” IEEE Trans. on Information Theory, vol. IT-26, pp.37-43, 1980.
[33]R.J. McEliece and E.R. Rodemich, “The Constantin-Rao construction for binary asymmetric error-correcting codes,” Inform. Contr., vol. 44, pp.187-196, l980.
[34]W. W. Peterson and E.J. Weldon, Error Correcting Codes, 2nd ed. Cambridge, MA: M.I.T. press, l972.
[35]D. T. Tang and L. R. Bahl, “Block codes for a class of constrained noiseless channels,” Inform. Contr., vol. 17, pp.436-461, l970.
[36]J.M. Berger, “A note on error detecting codes for asymmetric channels,” Inform. Contr., vol. 4, pp.68-73, Mar. l961.