Al-Qaeda's deputy leader has claimed that a radical Algerian Islamist group has joined al-Qaeda and is being urged to punish France
Ayman al-Zawahiri appeared in a video on a website on the fifth anniversary of the 11 September attacks.
In the tape, he issued a warning of new attacks targeting Israel and the Gulf.
Although France's government opposed the US-led war in Iraq, French officials believe the country is still a target for Islamist militants.
In the video, Zawahiri says: "Osama Bin Laden has told me to announce to Muslims that the GSPC [the Salafist Group for Preaching and Combat] has joined al-Qaeda," according to the transcript of his message given by the AFP news agency.
"This should be a source of chagrin, frustration and sadness for the apostates [of the regime in Algeria], the treacherous sons of [former colonial power] France."
He urges the group to become "a bone in the throat of the American and French crusaders".
"We pray to God that our brothers from the GSPC succeed in causing harm to the top members of the crusader coalition, and particularly their leader, the vicious America," he says.
Anne Giudicelli, head of the Terrorisc security consultancy who reviewed the whole tape, told Le Figaro newspaper the anti-France message had dominated the homepage of the website used by the GSPC for the past few days.
On Thursday, the GSPC pledged its allegiance to Osama Bin Laden and vowed to pursue jihad in Algeria, according to a statement posted on the internet, AFP reports.
"We pledge allegiance to Sheikh Osama Bin Laden... We will pursue our jihad in Algeria. Our soldiers are at his call so that he may strike who and where he likes," said the statement, signed by Abu Mossaab Abdelwadud, the emir of the group.
On Thursday, France's interior ministry said Zawahiri's comments "confirmed the high level of threat against our country", officials told AFP.
Ministry officials add al-Qaeda had announced in a statement on 11 September 2003 that the GSPC was one of its components and there have since been other threats issued against France.
On Monday, Pierre de Bousquet de Florian, head of the DST domestic security service, said the threat of terrorist attack in France remained "very high and very international".
"For our Islamist adversaries, our country is frankly in the Western camp, the crusaders in their words, and we will be spared nothing," he told French radio.
The GSPC was created in the late 1990s by members of the Armed Islamic Group (GIA), which the aim of establishing an Islamic state in Algeria.
The GIA and other militant groups waged a decade-long campaign of violence, following the annulment in 1992 of elections which Islamic groups were poised to win.
An estimated 150,000 people are thought to have been killed in the violence.
Last year, the GSPC singled out France as its "enemy number one" and issued a call for action against the country.
The GIA, which accused Paris of supporting the Algerian government, was blamed for a series of bombings in France in 1995.
al-Qaida Joins Algerians Against France
Special Analysis: Al-Qaeda's African Arm
Terror suspect deported from UK
France: Islamists Linked With Al Qaeda Threaten Terror