14 Widely Distributed File System Using Secret Sharing Scheme 1055115 24 2 2003 RAID RAID
Widely Distributed File System Using Secret Sharing Scheme FUNAHASHI Sekiji The data of keeping storages explosively increase and data control method of storage technology is more important.  RAID and Backup which is one of most important storage technology is originally to get high reliability and performance for a magnetic disk.  Therefore distributed store method using RAID and Backup couldn’t have enough safety of cracking and disasters. We present data distributed management method using Secret Sharing Scheme for high safety of security and disasters.  it’s method and RAID and backup compared with the result that distribution data of it’s method have enough safety of cracking and disasters.  Also it is easy to manage distribution data and distribute using network so that implementation with file system is optimum. And so we implement the file system using it and as a result it performed as good speed in small block size. key words Secret Sharing Scheme, Distrubuted store method, Distributed File Sys- tem
77 44 46 47
11 1.1 NAS *3 RAID SAN *2 RAID *1 RAID 1.2 1.2 2 33 44 55 6 (k, n) v v 2 1988 RAID [4] SAN *1 NFS/CIFS IP NAS *2 RAID SAN NAS 2.1
2.1
2.1
2.2 2.1.1 11 write 2.1.2 2.2 RAID 2 open close read 11
close read  write 2.3 2.2.1 RAID 2.2.2 RAID 0  5 RAID RAID5 11 2.3 SAN NAS SAN 2.3.1 SAN Fibre Channel SCSI-3 Fibre Channel 2Gb/s 10km 2.2 SAN 2.2 C 44 2.2 SAN Fig.2.2 Structure of SAN.
2.3.2
NAS
NAS IP NFS/CIFS NFS/CIFS 2.3 NAS
44 2.3 NAS 3 — (Secret Sharing Scheme) (k,n) 1979 Shamir [1] Blakley [2] [3] ( ) ( ) Shamir (k, d, n) Shamir (k, n) Shamir (k, n) 2 (k, n) 2
3.1 3.1 3.1.1 W (3.1) U S U U S' U S' H (S|U) = 0 (3.2) X X S' ) (3.4) log | S | log2 |W i | ≥ H(W i ) ≥ H(S) = log2 |S| (3.5) S W U S 11 S 11 X S' H(S|X) = H(S) (3.3) (3.4) S | S| ( – 10 – log₂ |W | = log₂ |Ṣ |
3.1.2 (k, n) Shamir
n k
n
S
GF(p) 1. GF(p) n
n < p 2. GF(p)
3.
W i (i = 1, . . ,n) 4. x i
1.
x i j (1 ≤ j ≤ k,k < n)
ls
– 11 –
0 3.1 3. k k:
S' (3.7) 1
(mod p) (mod p)
S + r1xn + r2xn2 + = Wn (mod p)
GF(p) a X1, X2, . . . , Xn

3.1.3
(k, d, n)
(k, d, n)
k k – d
k: S
, k > d Sι(l = 0, 1, . . . , d) w;(i = 1, 2, . . . , n) α r j (j = 1, 2, . . . , k − d) p (3.12) wi = S0 + S1α + S2α² + · · + Sdα d + r1α d+1 + · · · + rk_dαk-1 (mod p ) 3.2 Shamir (k, n) Shamir (k, n) 3.3
2
Shamir (k, n) (3.7) Xi GF(p) a p 2 n GF(2n) GF(2) m – 1 Xm GF(2) m P(x) Xm F1(x) F2(x) F1(x)F2(x) P(x) F1(x)F2(x) (mod P(x))
Xm

– 14 –
4 NAS RAID SAN RAID 4.1 RAID (k, n) n n k: (k, n) 4.1 (b) (a) (k, n) 1      1 4.2 1. 2. (k,n) 3. n 4. 1. 2. 3. k
1
2
4. (k,n) 1. 2. k: 3. (k,n) 4. (k,n) 4.3 5. n 4.3 RAID5 RAID5 4.3.1 RAID5 4.1 (k, n) RAID5 1 y y + 1
1 n T 1 x + 1 + 1 1 (n, x, y ) RAID5 (k, n)
RAID5 1 1
y – 1 n RAID5 4.2 y 4.2 S α B 77 α ≪ s, β ≪ s, γ ≪ s
4.1 4.2 4.3.2 RAID5 4.3
2 ≤ k ≤ n k RAID5 1 2 x + 1 + 1 y + 1 RAID5 2 RAID5 RAID5 3 RAID5 (k, n) lis 2 k: 0 4.4
NAS IP Network Fibre Channel Fibre Channel IP Network Fibre Channel 4.4
3 . . . Fibre Channel IP Network IP Network NFS IP Netwrok Fibre Channel 10km 4.5 4.5
× 5 UNIX FFS*1
VFS(Virtual File System) v
VFS v v v [6] UFS *4 NFS
FreeBSD
*1 Fast File System *² Remote File Sharing *3 Network File System *4 Unix File System. VFS FFS v v 5.1 / UFS NFS 1 / / / SML (Share Management Layer) Distribution Layer) SML SDL (Share SSFS (Secrect Sharing File System) SDL (Share Distribution Layer) 5.1 5.1 SSFS SDL SDL 1 1 VFS SDL NFS 5.2 5.2 1 3 5.1 Fig. 5.1 Filesystem of local host. 5.2 Fig. 5.2 File system with remote host .
SSFS
5.2
v
vfs/v v V UFS i NFS 1 v SML SSFS SDL 5.3 5.3 SDL UFS NFS v
5.3 SML SDL v Fig. 5.3 v node of SML and SDL.
5.3
SSFS
v
v /vfs v FreeBSD read write   rename 54 2 1 v ● V . v SSFS v 5.3.1 v SSFS 5.1 SSFS /
write read SSFS SDL v SSFS SDL v 5.4 SML SDL v 5.4 SSFS v setattr UFS NFS setattr 5.4 SSFS 1 Fig. 5.4 v node operation of SSFS 1. getattr SDL v V v 1 UFS getattr
5.5

5.3.2
SSFS read write 5.6 5.6 start end SSS 5.5 2 Fig. 5.5 v node operation of SSFS 2. 5.6 Fig. 5.6 SSS Blcok. write 1. a 2 b SDL k: v SSFS 5.3 SSFS     v 2. 3. (3.9) 1. 2. SDL    v k 3. a b i. ii.
5.7
5.7 file system buffer logical file block 5.8
5.8
file SSS block system buffer logical file block 5.8 Fig. 5.8 SSS block. 5.3.3 v SSFS lookup lookup SSFS SDL v lookup v 2 lookup v v SSFS SDL v 1 lookup SSFS lookup 1. a 2 b 2. a b 3. a b 5.4 SML SDL v lookup v key
SDL h 3 1 SDL k: SDL 2 2.1 2.2 2.2.1 2.2.2 3 5.5 SDL v mount vfs 5.9 FreeBSD vfs 5.9 Fig. 5.9 vfs object and mount. 1 SDL SSFS RAID [7] 1 1 vfs 1.UFS 2.NFS 3.UFS 4.NFS 5.NFS vfs vfs 4 5 2 5 1 UFS UFS 2        5 SSFS 1          vfs SDL 1 vfs vfs SDL      v SSFS 1 6
SSFS
6.1
SSFS (k, n) n k: L SDL
SSFS
E D W SDL I SDL R
スSSFS
n
– 36 – SSFS SDL
SDL
6.2 6.2.1 OS FreeBSD 5-CURRENT (2002/10/24) Compiler   gcc version 3.2.1 PentiumII 400MHz CPU HDD   IDE ATA-33 4096Byte 8192Byte 16384Byte 1024Byte   2048Byte 32768Byte 65536Byte   262144Byte   524288Byte 1048576Byte 11
v
6.2.2
6.1 6.1

6.2
6.2 32Byte   16Byte   8Byte   4Byte 6.1 Fig. 6.1 Transaction time of encrypt. 6.3 6.3 6.4 6.3 (6.3) 6.2
SDL 6.1 6.3
1MB T
32Byte
1MB
48 File size (KB) 6.2 Fig. 6.2 Transaction time of dynamic and static inverse matrix.
6.3 6.4 1
7 v  GF(2 n ) GF(2n) IP Network SCSI over IP [8] C David Greene David Greene
[3] 14. 1997.
Aug. 2000. Vol.2000, No.74   pp.79–84 [8] RFC3347, "Small computer systems interface protocol over the internet (iscsi) re- quirements and design considerations," , July 2002. [9] c. 8 2000. [10] U. Vahalia UNIX 2000 [11]
FreeBSD
1998.
[12] S.J.Leffler, M.K.Mckusick, M.J.Karels, and J.S.Quarterman, The Design and Im- plementation of the 4.3BSD UNIX Operating System, 3　, . [13] B. Callaghan   NFS 2001 [14] 3. 2 . [15] RAID 2000. [16] W.C. Preston   SAN & NAS 2002 . [17] 14 . [18]し” Vol.1, pp.235–238   Dec. 2002.