(Recasts with possible move to Algeria, edits)

By Tarek Amara

TUNIS, March 10 (Reuters) - Al Qaeda said on Monday it had kidnapped two Austrian tourists in Tunisia on Feb. 22, linking its action to an Israeli offensive in Gaza, and suggested it had since moved the captives to neighbouring Algeria.

Tunisia said it had launched an air and land search for the Austrians, but it had no proof they were still on its territory.

Al Jazeera television aired an audio recording by a man who identified himself as Salah Abou-Mohammad -- a spokesman for al Qaeda Organisation in the Islamic Maghreb -- who said the group would announce soon its terms for the release of the hostages.

A separate al Qaeda statement suggested the group had taken the two across the border into Algeria, al Qaeda's north Africa base and a mostly-desert country 4-1/2 times the size of France.

Abou-Mohammad said the two were in good condition but warned Westerners against visiting the north African state, which attracts tourists from many European countries.

Western tourists were "searching for pleasures in Tunisia while our folk in Gaza are being slaughtered by the Jews with consent from Western countries whose governments are killing our brothers in every (Muslim) country", he said.

Israel last week ended an offensive which killed 120 Palestinians in Gaza.

Austrian media have identified the tourists as Andrea Kloiber, 43, and Wolfgang Ebner, 51 -- a couple from near Salzburg. Abou-Mohammad said they were a nurse and a consultant and gave similar-sounding names.

"We also inform the State of Austria that any military action by the apostate Algerian state to free the abductees will put their lives at risk," the group said, according to a statement reported by U.S.-based SITE Intelligence Group.

North African states are increasing security cooperation to try to stifle attempts by radical Islamist groups to coordinate attacks on targets both in the region and in Europe.

SECURITY THREAT

A Tunisian government statement said the two Austrians were last heard of crossing the Sahara in a direction that would have taken them beyond Tunisian borders.

"Until now there is no element that proves that the two Austrian citizens are in Tunisian territory or that they were kidnapped inside Tunisian borders," it added.

Serious breaches of security are rare in Tunisia, a Mediterranean Arab country most Europeans know only as a sleepy holiday destination and which borders Libya and Algeria.

But in 2002, 14 Germans, five Tunisians and two French people were killed when a suicide bomber rammed a tanker truck filled with cooking gas into a Jewish shrine.

The bombing on the southern island of Djerba, Tunisia's main tourist destination, was the first attack claimed by al Qaeda in an Arab country after the Sept. 11 attacks in the United States.

Family members of the Austrian couple launched a publicity campaign to try to find them before the al Qaeda statement.

Bernhard Ebner said last week his father had been to the desert every year since 2000. "It (Tunisia) is not a new country for him," he said.

An Austrian foreign ministry spokesman said the two were officially classified as missing and the government was trying to verify reports they had been abducted. (Additional reporting by Inal Ersan in Dubai and Alexandra Zawadil in Vienna; editing by Andrew Roche) (For full Reuters Africa coverage and to have your say on the top issues, visit: http://africa.reuters.com/ )

AlertNet news is provided by