200306109 ⑴ 玖、發明說明 【發明所屬之技術領域】 本發明是有關於一種數位資料的編碼程序，係利用一 種以長度爲一固定預設長度之區塊來進行編碼的演算法。 【先前技術】 數位資料於傳輸時，是以資料流的形態進行交換。依 據現今所使用的標準，特別是 MPEG-2 ( Motion Picture Expert Group version 2)標準，這種資料流必需由可傳送 之封包所構成。 當資料必需編碼時，一些所用的編碼演算法都需要將 資料封包分割成許多固定預設長度的區塊後，以便能夠以 一編碼鑰匙對其進行編碼。而該等區塊之長度則視所選擇 的編碼演算法而定。 一般而言，由於訊息或資料封包的長度通常都不是該 預設區塊長度的整數倍，所以將封包分割成區塊之後，會 產生一個長度小於預設定値的剩餘區塊。在很多情形下， 尤其是MPEG-2的資料流處理，此剩餘區塊不可被刻意塡 充加入資料，以使其長度增加至與預設長度相等。因此， 這個剩餘區塊就無法用一般的方式來編碼。 美國專利案5,684,8 76描述一個方法，可對長度超過 前述預設長度的訊息之剩餘區塊加密。在該方法中，將該 訊息或資料封包分割成固定預設長度的區塊之後，所得到 的最後一個完整區塊，先對其編碼。從這個經過編碼之完 -6 - (2) (2)200306109 整區塊中取出與剩餘區塊等長的一部份，構成了整個加密 訊息的一部份。其餘未被取出的部份則與剩餘區塊組合， 形成一個長度爲預設長度的區塊，此區塊因而可使用傳統 的方式來編碼。由於在以上所有步驟中，封包的長度都維 持不變，因此該方法可相容於如MPEG2等之類的標準。 然而’這個方法牽涉到需要至少一完整的區塊；否則 即不適用。換言之’如果封包的長度小於該預設長度時， 就無法使用這個方法。 【發明內容】 本發明目的在於提供一種方法，可以對不同長度的區 塊予以編碼，不受訊息長度的限制，以解決先前技術的缺 點。 達成此目標的方法如前言所述，而其特徵包含以下步 驟：定義一長度小於固定預設長度的剩餘區塊；形成具有 該固定預設長度之混合區塊，此混合區塊具有一已知之預 設値，且與所欲編碼的資料無關；對此混合區塊編碼以形 成一經過編碼之混合區塊；從該經過編碼之混合區塊中取 出一有用部份，此有用部分具有與剩餘區塊相等之長度； 再將經過編碼之混合區塊中所取出的有用部份與該剩餘區 塊混合，以得到一經過編碼之剩餘區塊，而其具有與原始 剩餘區塊相等之長度。 【實施方式】 -7- (3) (3)200306109 如第1圖及第2圖所示，其中數位資料1 〇將要被加 密。舉例而言，此數位資料可能是一筆即將被傳送的訊息 ，或是一資料流分解後其中的一個資料封包。依據本發明 之方法，首先將該資料分割成長度皆爲一預設長度D (例 如8個位元組）之區塊Μ1、M2.......。如果該資料的 長度剛好是此預設定値的整數倍，則每一個區塊可使用傳 統方式的編碼演算法加以編碼。應注意的是，圖中雖以縮 寫爲ECB的電子密碼簿（Electronic Code Book)作爲編 碼方式之代表，但仍可採用其它的編碼方式，特別是縮寫 爲 CBC ( Cipher Block Chaining )的區段連鎖編碼方式 ，而且也不以這兩種方式爲限。如習於此技藝者所皆知， 在編碼時，需使用到一編碼鑰匙。如果該資料長度小於前 述預設定値，則只會有一個剩餘區塊，而不會有長度爲該 預設定値的完整區塊出現。如果該資料長度超過預設値D ，但卻不是D的整數倍，則該資料在分解成區塊後，會 形成一個長度（e )小於D的不完全區塊，稱之爲剩餘區 塊（residual block代號BR)。因此，該資料於分解後， 可能只有一個剩餘區塊，也可能還有完整的區塊。 如前所述，有些標準規定在編碼過程的每一步驟中， 訊息或封包的長度需維持一定。而區塊式的編碼演算法也 僅適用於具有固定預設長度之區塊。根據本發明所提出之 方法，其中包含一特別的步驟，係將該剩餘區塊（BR ) 與一混合區塊 （combination block，代號BC)相混合， 以得到一經過編碼之區塊。該混合區塊的特徵則容後詳述 -8- (4) (4)200306109 第1圖爲本方法的第一種實施例之說明，其中混合區 塊（B C )是由長度爲D個位元組的已知結構所構成。依 據另一個有利之實施例，此區塊是由完全相同的D個位 元組所組成，而各位元組的數値則是以OxFF爲例。 以本方法之一步驟，亦即第1圖、第2圖及第4圖中 所示之CFR編碼方式，首先對混合區塊（BC )編碼，以 得到經過編碼而具有前述固定預設長度D之區塊（BC 5 ) 。再將該經過編碼之混合區塊（B C ’）的一部份取出。所 取出部份，稱之爲有用部份（PU )，其長度（e )則必需 與剩餘區塊的長度相等。該有用部份通常是將經過編碼之 混合區塊的右邊部份切割取出，或將左邊部份切割取出。 然而，也可以考慮其它的方式，如以下參照第3 b圖至第 3 d圖之說明。 從經過編碼之混合區塊（BCT )取出的有用部份（PU )，再與剩餘區塊一起經過一互斥或（XOR)函數的作用 ，以產生一經過編碼之剩餘區塊（BR5 )，此區塊具有與 剩餘區塊相等之長度（e )，而其內含之資料來自剩餘區 塊（BR )，並且是經過編碼的形態。 因此，儘管混合區塊（B C )的數値可能被知悉，但 由互斥或（XOR )函數作用後所得到經過編碼之剩餘區塊 (BR’），其中所含的資訊不會被未經授權的第三者所取 得，所以可以安全地傳送；另一方面，第三者若能取得鑰 匙，可被允許對混合區塊編碼，而得知經過編碼之混合區 -9- (5) (5)200306109 塊（B C ’）的內容，進而推導出原始剩餘區塊（B R )的內 容。 從第1圖可推知，分解自資料封包1 0之區塊Μ1、 Μ2.......等，具有前述固定預設之長度D，係使用傳統 編碼方式，如 E C B ” ，來予以編碼，進而產生經過編碼 之區塊C 1、C2.......等。編碼後之訊息長度與原始訊 息的長度相同，符合先前所提之需求。 本方法第二個實施例如第2圖所示，其中，所要傳送 的訊息1 〇或每個資料封包之前都有一個標頭（Η )。此 標頭通常包含一固定部份與一變動部份，每一封包的標頭 之固定部份都相同，變動部份則可以爲封包的識別碼（ PID )等。混合區塊（Bc )則是由標頭（Η )之全部或一 部份，加上一塡充向量（filling vector VR)而形成。若 標頭之長度小於或等於預設定値D時，則可使用其全部 ;若是標頭長度過長，則可將其截取至該預設長度。 也可以只取用標頭中的一部份，特別是變動部份。當 選定取出之部分後，通常藉由一個互斥或（X0R)函數， 再與塡充向量（VR )相混合，以形成前述的混合區塊（ B C )。因此，每當有剩餘區塊要傳送時，會從不同的混 合區塊（B C )開始對該剩餘區塊加以編碼。這樣可以增 強資料傳送的安全性，而任何第三者，若知道標頭內容及 編碼所用鑰匙，仍可加以解碼。應注意的是，標頭在傳送 時，其內容通常是未經過編碼或任何修飾的。 前述之塡充向量（VR)，舉例而言，可由內含全部 -10- (6) (6)200306109 爲常數値（如〇Xff)之區塊所構成，其目的是要補齊標頭 或標頭中被選用之部份，以形成一具有固定預設長度D 的混合區塊（B C )。 如同先前之實施例，混合區塊（B C )形成之後，首 先需經過編碼，然後再從中取出有用部份（PU )，來與 所要傳送的剩餘區塊相混合。 要從經過編碼之混合區塊中取出有用部份（PU )， 可使用不同的方法，例如在第3 b至第3 d圖中所揭示者。 比如，在第3 b圖中，是取該區塊靠左邊的部份，而在第 3 d圖中，則是取其靠右邊的部份。 也可以根據與區塊內容有關的一定規則來選取有用的 部分’例如：依照標頭（Η )內容，依照經過編碼之混合 區塊（B C，）內容，或者是依照訊息編碼及解碼雙方都知 曉的其它區塊內容。舉例而言，可以先確定一個標頭的値 ’再依據這個値來選擇經過編碼之混合區塊（B C，）的向 右位移量Δ。這正是第3 c圖所揭示的情形；其中位移量 △，是以與區塊左邊圖示距離爲二個位元組來代表。另外 ，也可以將經過編碼的混合區塊之數値，與另一事先定好 之固定數値作模數（module)運算，來決定位移量。凡是 任何規則，只要可以淸楚明確地決定一位移量，而且又爲 訊息解碼之一方所知悉者，都可適用。 在此特別的實施例中，其擷取有效部份的方式隱含著 編碼結果會定期產生變化，使得破解更爲複雜，因此可以 增進編碼的安全性。然而此方法並不會帶來“連鎖錯誤” -11 - (7) (7)200306109 ，也就是說，若有一個錯誤發生，對後續的編碼並不會有 任何影響。 訊息的解碼是以與編碼時相反的程序來達成，其詳細 過程揭示於第4圖。其中，接收到訊息的一方或裝置，依 照傳統的方式，將該訊息分割成長度爲預設定値D的區 塊。就如同原始訊息在編碼時的情況一樣，所接收到經過 編碼的訊息，在分割之後，會留下一個長度爲e ( <D ) 的剩餘區塊B R ’。對於每個長度爲D之區塊C 1、C 2、 · · • ···等，則施予傳統的解碼演算法，以得到原來的區塊200306109 ⑴ 玖, description of the invention [Technical field to which the invention belongs] The present invention relates to an encoding program for digital data, which uses an algorithm that encodes a block with a length of a fixed preset length. [Prior art] When digital data is transmitted, it is exchanged in the form of a data stream. According to the standards used today, especially the MPEG-2 (Motion Picture Expert Group version 2) standard, this data stream must consist of packets that can be transmitted. When data must be encoded, some of the encoding algorithms used need to divide the data packet into a number of fixed-length blocks so that it can be encoded with an encoding key. The length of these blocks depends on the chosen encoding algorithm. Generally speaking, since the length of a message or data packet is usually not an integer multiple of the length of the preset block, after the packet is divided into blocks, a remaining block with a length less than a preset value is generated. In many cases, especially for MPEG-2 data stream processing, this remaining block cannot be intentionally added with data to increase its length to be equal to the preset length. Therefore, this remaining block cannot be encoded in the usual way. U.S. Patent No. 5,684,8 76 describes a method for encrypting the remaining blocks of a message longer than the aforementioned preset length. In this method, after the message or data packet is divided into blocks of a fixed preset length, the last complete block obtained is encoded first. From this encoded block, a part equal to the length of the remaining block is taken out, which constitutes a part of the entire encrypted message. The remaining unextracted parts are combined with the remaining blocks to form a block with a preset length. This block can therefore be encoded using traditional methods. Since the packet length remains the same in all the above steps, the method is compatible with standards such as MPEG2. However, this method involves at least one complete block; otherwise it is not applicable. In other words, 'If the length of the packet is less than the preset length, this method cannot be used. SUMMARY OF THE INVENTION The purpose of the present invention is to provide a method that can encode blocks of different lengths without being limited by the length of the message to solve the shortcomings of the prior art. The method for achieving this goal is as described in the introduction, and its characteristics include the following steps: define a remaining block with a length less than a fixed preset length; form a mixed block with the fixed preset length, and the mixed block has a known Preset 値, and has nothing to do with the data to be encoded; encode this mixed block to form an encoded mixed block; take a useful part from the encoded mixed block, this useful part has the same as the remaining The blocks are equal in length; the useful parts taken out from the coded mixed block are mixed with the remaining blocks to obtain a coded remaining block with a length equal to the original remaining block. [Embodiment] -7- (3) (3) 200306109 As shown in Fig. 1 and Fig. 2, the digital data 10 will be encrypted. For example, this digital data may be a message to be sent, or a data packet after a data stream is decomposed. According to the method of the present invention, the data is first divided into blocks M1, M2,... Each having a length D (for example, 8 bytes). If the length of the data is exactly an integer multiple of this preset value, each block can be encoded using a conventional encoding algorithm. It should be noted that although the Electronic Code Book abbreviated as ECB is used as the encoding method in the figure, other encoding methods may be used, especially the sector chain abbreviated as CBC (Cipher Block Chaining). The encoding method, and not limited to these two methods. As is known to those skilled in the art, a coding key is used when coding. If the length of the data is shorter than the pre-defined frame, there will be only one remaining block, and there will be no complete block with the length of the preset frame. If the length of the data exceeds the preset 値 D, but it is not an integer multiple of D, after the data is decomposed into blocks, an incomplete block with a length (e) less than D is formed, which is called the remaining block ( residual block code BR). Therefore, after the data is decomposed, there may be only one remaining block, or there may be complete blocks. As mentioned earlier, some standards require that the length of a message or packet be maintained at each step of the encoding process. The block-based encoding algorithm is only applicable to blocks with a fixed preset length. The method according to the present invention includes a special step of mixing the remaining block (BR) with a combination block (code: BC) to obtain an encoded block. The characteristics of this mixed block will be detailed later. (4) (4) 200306109 Figure 1 illustrates the first embodiment of the method, where the mixed block (BC) is composed of D bits. The tuple consists of a known structure. According to another advantageous embodiment, the block is composed of exactly the same D bytes, and the number of each byte is taken as an example of OxFF. In one step of the method, that is, the CFR encoding method shown in FIG. 1, FIG. 2, and FIG. 4, first, the mixed block (BC) is encoded to obtain an encoded code having the aforementioned fixed preset length D. Block (BC 5). Then take out a part of the coded mixed block (B C ′). The extracted part is called the useful part (PU), and its length (e) must be equal to the length of the remaining blocks. The useful part is usually the right part of the coded mixed block is cut out, or the left part is cut out. However, other methods can also be considered, such as the following description with reference to Figures 3b to 3d. The useful part (PU) taken from the coded mixed block (BCT) is then subjected to a mutex or (XOR) function with the remaining blocks to generate a coded remaining block (BR5), This block has the same length (e) as the remaining block, and the data contained in it comes from the remaining block (BR) and is in the form of encoding. Therefore, although the data of the mixed block (BC) may be known, the information contained in the coded remaining block (BR ') obtained by the function of the mutex or (XOR) function will not be unauthorised. Obtained by an authorized third party, so it can be transmitted securely; on the other hand, if the third party can obtain the key, it can be allowed to encode the mixed block and learn the encoded mixed region-9- (5) ( 5) The contents of the 200306109 block (BC '), and then the content of the original remaining block (BR) is derived. It can be inferred from Figure 1 that the blocks M1, M2, etc., which are decomposed from the data packet 10, have the aforementioned fixed preset length D, and are encoded using traditional encoding methods, such as ECB ". Then, the coded blocks C 1, C2, etc. are generated. The length of the coded message is the same as the length of the original message, which meets the requirements previously mentioned. The second embodiment of this method is shown in Figure 2 As shown in the figure, the message to be transmitted 10 or each data packet has a header (Η). This header usually includes a fixed part and a variable part, and the fixed part of the header of each packet The share is the same, the change part can be the packet identification code (PID), etc. The mixed block (Bc) is the whole or a part of the header (Η), plus a filling vector VR ). If the length of the header is less than or equal to the preset 値 D, all of them can be used; if the length of the header is too long, it can be truncated to the preset length. You can also use only the header Part, especially the changing part. When selecting the part to be taken out, usually by A mutual exclusion or (X0R) function is then mixed with the charge vector (VR) to form the aforementioned mixed block (BC). Therefore, whenever there is a remaining block to be transmitted, it will be from a different mixed block (BC) began to encode the remaining blocks. This can enhance the security of data transmission, and any third party can still decode the header content and the key used for encoding. It should be noted that the header is in When transmitting, its content is usually unencoded or modified in any way. The aforementioned charge vector (VR), for example, can contain all -10- (6) (6) 200306109 as a constant 値 (such as 〇Xff) The purpose is to complete the header or selected part of the header to form a mixed block (BC) with a fixed preset length D. As in the previous embodiment, the mixed block After the (BC) is formed, it needs to be encoded first, and then the useful part (PU) is taken out from it to be mixed with the remaining blocks to be transmitted. To take out the useful part (PU) from the encoded mixed block, Different methods can be used, such as in section 3b To the one disclosed in Figure 3d. For example, in Figure 3b, the left part of the block is taken, and in Figure 3d, the right part is taken. It is also possible Select useful parts according to certain rules related to the content of the block ', for example, according to the content of the header (Η), the content of the coded mixed block (BC,), or other information known to both the encoding and decoding of the message The content of the block. For example, you can first determine the header 値 'and then select the rightward displacement Δ of the coded mixed block (BC,) based on this 値. This is what is shown in Figure 3c Case; where the displacement △ is represented by two bytes from the distance shown on the left of the block. In addition, the number of encoded mixed blocks can also be used as a module operation with another fixed number determined in advance to determine the displacement. Any rule can be applied as long as it can clearly determine an amount of displacement and is known to the party that decodes the message. In this particular embodiment, the way in which the effective part is retrieved implies that the encoding result will change periodically, making cracking more complex, and thus improving the security of the encoding. However, this method does not bring "cascading errors" -11-(7) (7) 200306109, that is, if an error occurs, it will not have any impact on subsequent encoding. The decoding of the message is achieved by the reverse procedure of the encoding. The detailed process is shown in Figure 4. Among them, the party or device receiving the message divides the message into blocks of length 値 D according to the traditional method. Just as in the case of encoding the original message, after receiving the encoded message, after the segmentation, a remaining block B R ′ of length e (< D) is left. For each block C 1, C 2, ·····, etc. of length D, a traditional decoding algorithm is applied to obtain the original block
Ml ' M2 ......等。而對於混合區塊（B C )則施予與原 先編碼時一樣的編碼演算法，然後按照先前在編碼時所使 用的規則，從經過編碼之混合區塊（B C ’）中取出有用部 份（PU )。再將加密過之剩餘區塊（BR’ ）與經過編碼 之混合區塊中所取出的有用部份（PU )來作邏輯函數互 斥或（X O R )運算，可得到原始的剩餘區塊（B R 5 )，整 個訊息因而得以重現。 若混合區塊包含有標頭時，因爲此處所使用的標頭於 傳送時，並未經過任何編碼或修飾，所以整個訊息仍可按 照上述方法重建。 依據本發明，混合區塊可以是固定不變，也可加以修 飾變化。只要變化的規則爲訊息編碼的一方，或需要解碼 的一方所知悉，任何的變化皆可進行。當混合區塊有所變 化時，要破解剩餘區塊就更加複雜。 本發明具有能夠將任意一訊息，不論其長度爲何，予 -12- (8) (8)200306109 以加密的優點，特別是即使該訊息的長度小於預設定値D 時亦然。由於訊息中所有成分都經過編碼，所以可以確保 對於未經授權讀取之最佳防範。本發明還可允許只使用一 種編碼演算法即可滿足所有加密的需求，而免除了在高速 的區塊式編碼之外，還要一個用於剩餘區塊之連續式編碼 的需要。除此之外，本發明的編碼程序不但極易施行，所 提供之防範破解安全度也極高。 【圖示簡單說明】 本發明及其優點，配合參考以下較佳實施例之說明及 圖示，應可更淸楚地明瞭，其中： 第1圖爲本發明之第一個較佳實施例之示意圖 第2圖爲本發明之第二個較佳實施例之示意圖 第3 a圖爲經過編碼之混合區塊之示意圖 第3 b圖爲從第3 a圖中經過編碼之混合區塊左邊取出 一有用部份之示意圖 · 第3 c圖爲依據混合區塊所定義之位移量而從第3 a圖 中經過編碼之混合區塊取出一*有用部份之不思圖 第3 d圖爲從第3 a圖中經過編碼之混合區塊右邊取出 一有用部份之不意圖 第4圖爲將本發明第一個較佳實施例中編碼所得之訊 息予以解碼之示意圖 -13-Ml 'M2 ... etc. For the mixed block (BC), the same encoding algorithm as the original encoding is applied, and then the useful part (PU) is extracted from the encoded mixed block (BC ') according to the rules used in the previous encoding. ). The encrypted residual block (BR ') and the useful part (PU) extracted from the coded mixed block are used to perform a logical function mutual exclusion or (XOR) operation to obtain the original residual block (BR). 5), the entire message is thus reproduced. If the mixed block contains headers, because the headers used here are transmitted without any encoding or modification, the entire message can still be reconstructed as described above. According to the present invention, the hybrid block may be fixed or modified. As long as the changing rules are known to the party encoding the message or the party needing decoding, any changes can be made. When the hybrid block changes, it is more complicated to crack the remaining blocks. The present invention has the advantage of being able to encrypt any message, regardless of its length, with -12- (8) (8) 200306109, especially if the length of the message is less than the preset 値 D. Since all components of the message are coded, the best protection against unauthorized reading is ensured. The present invention also allows all encryption needs to be met using only one encoding algorithm, eliminating the need for continuous encoding for the remaining blocks in addition to high-speed block encoding. In addition, the encoding program of the present invention is not only easy to implement, but also provides high security against cracking. [Brief description of the drawings] The present invention and its advantages, with reference to the description and illustration of the following preferred embodiments, should be more clearly understood, of which: Figure 1 is the first preferred embodiment of the present invention Schematic diagram 2 is a schematic diagram of a second preferred embodiment of the present invention. Fig. 3a is a diagram of a coded mixed block. Fig. 3b is a diagram taken from the left of the coded mixed block in Fig. 3a. Schematic diagram of the useful part. Fig. 3c is a block diagram of the useful part taken from the encoded mixed block in Fig. 3a according to the amount of displacement defined by the mixed block. The intention of extracting a useful part to the right of the coded mixed block in Figure 3a is shown in Figure 4. Figure 4 is a schematic diagram that decodes the encoded information in the first preferred embodiment of the present invention.